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

摘要

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.%图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.