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

Total chromatic number of planar graphs with few short cycles

作　　者：薛玲[1] 吴建良[2] 

机构地区：[1]泰山职业技术学院信息工程系,山东泰安271000 [2]山东大学数学学院,山东济南250100

出　　处：《山东大学学报（理学版）》2012年第9期84-87,共4页Journal of Shandong University(Natural Science)

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

摘　　要：图G的k-全染色是用k种颜色对图G的V(G)∪E(G)中的元素进行着色,使得相邻或者相关联的两个元素染不同的颜色,图G的全色数是使G存在k-全染色的最小整数k.对最大度为Δ的平面图,如果(1),Δ(G)≥5且任何点至多关联一个长度至多为5的圈,或者(2),Δ≥4,不含3-圈并且任何点至多关联一个长度至多为6的圈,则它的全色数为Δ(G)+1。A total k-coloring of a graph G is acoloring of V（G） UE（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 （1）Δ（G）≥5and 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.

关 键 词：平面图 全染色 圈 全色数 

分 类 号：O157.5[理学—数学]