CAJ | 학술논문

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