您的位置:山东大学 -> 科技期刊社 -> 《山东大学学报(理学版)》

J4 ›› 2012, Vol. 47 ›› Issue (9): 84-87.

• 数学 • 上一篇    下一篇

较少短圈的平面图的全色数

薛玲1, 吴建良2*   

  1. 1. 泰山职业技术学院信息工程系, 山东 泰安  271000;
    2. 山东大学数学学院, 山东 济南 250100
  • 收稿日期:2010-09-15 出版日期:2012-09-20 发布日期:2012-09-24
  • 通讯作者: 吴建良(1965- ), 男, 教授, 博导, 研究方向为图论及其应用. Email:jlwu@sdu.edu.cn
  • 作者简介:薛玲(1975- ), 女, 讲师, 硕士研究生, 研究方向为图论及其应用. Email:xuelingxue@yeah.net
  • 基金资助:

    国家自然科学基金资助项目(10971121)

Total chromatic number of planar graphs with few short cycles

XUE Ling1,  WU Jian-liang2*   

  1. 1. Department of Information Engineering, Taishan Polytechnic, Taian  271000, Shandong,  China;
    2. School of Mathematics, Shandong University, Jinan 250100, Shandong, China
  • Received:2010-09-15 Online:2012-09-20 Published:2012-09-24

摘要:

 图G的k-全染色是用k种颜色对图G的V(G)∪E(G)中的元素进行着色, 使得相邻或者相关联的两个元素染不同的颜色, 图G的全色数是使G存在k-全染色的最小整数k. 对最大度为Δ的平面图, 如果(1),Δ(G)≥5且任何点至多关联一个长度至多为5的圈, 或者(2),Δ≥4, 不含3-圈并且任何点至多关联一个长度至多为6的圈, 则它的全色数为Δ(G)+1。

关键词: 平面图; 全染色; 圈; 全色数

Abstract:

A total k-coloring of a graph G is acoloring of V(G)∪E(G) using k colors such that no two adjacent or incident elements receive the same color. The total chromatic number of G is the smallest integer k such that G has a total k-coloring. It is proved here that the total chromatic number of a planar graph G is Δ(G)+1 if (1) Δ≥5 and every vertex is incident with at most one cycle of length at most 5, or (2) Δ≥4, the girth g≥4 and every vertex is incident with at most one cycle of length at most 7.

Key words: planar graph; total coloring; cycle; total chromatic number

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!