围长较大的平面图的全染色的一个结果  

A Result from Full Dyeing of Planar Graphs with Large Girth

作　　者：张埂[1] 万慧敏[2] 古华华 扈丁文 

机构地区：[1]四川文理学院学报编辑部,四川达州635000 [2]中国矿业大学理学院,江苏徐州221008 [3]达县第四中学,四川达州635000

出　　处：《绵阳师范学院学报》2012年第2期8-10,共3页Journal of Mianyang Teachers＇ College

基　　金：中央高校基本科研业务费专项基金(2010LKSX06);四川文理学院2011年院级科研项目(2011Z008y)

摘　　要：图G的一个k全染色是用k种颜色对图G的顶点集和边集进行染色使得相邻接的或相关联的元素染不同的颜色,图G的全色数χ"(G)为图G的k-全染色中的最小k值.Behzad和Vizing猜想任意简单图G的全色数都不超过Δ(G)+2,已经证明了此猜想对最大度不是6的平面图成立,而且最大度不小于9的平面图G的全色数为Δ(G)+1.本文利用差值转移方法研究了最大度小于9的一些情况,证明了最大度为4,5,6,7,8的平面图G,如果其围长不小于8,则其全色数也为Δ(G)+1.A total k-coloring of a graph G is a coloring of V（G）∪E（G） using k colors such that no two adjacent or incident elements share the same color.The total chromatic number of G,denoted by χ＂（G）,is the smallest integer k such that G has a total k coloring.Behzad and Vizing conjectured that the total chromatic number of any graph G is no more than Δ（G）＋2.The conjecture has been verified to be true for planar graph when the maximum degree of G is not 6,furthermore,the total chromatic number of any planar graph G with maximum degree no less than 9 is Δ（G）＋1.In this paper,using discharging method,we studied the total coloring of planar graphs with maximum degree less than 9 and proved that the total chromatic number of planar graphs G with maximum degree 4,5,6,7,8 under the condition that the girth of G is at least 8 is Δ（G）＋1.

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

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