On total chromatic number of planar graphs without 4-cycles  

作　　者：Min-le SHANGGUAN 

机构地区：[1]College of Mathematics Physics and Information Engineering,Zhejiang Normal University

出　　处：《Science China Mathematics》2007年第1期81-86,共6页中国科学：数学（英文版）

基　　金：This work was partially supported by the National Natural Science Foundation of China (Grant No. 10471131)

摘　　要：Let G be a simple graph with maximum degree Δ(G) and total chromatic number x ve (G). Vizing conjectured that Δ(G) + 1 ? X ve (G) ? δ(G) + 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs is Δ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then x ve (G) ? 8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture.Let G be a simple graph with maximum degree A(G) and total chromatic number Xve(G). Vizing conjectured thatΔ(G) + 1≤Xve(G)≤Δ(G) + 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs isΔ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then Xve(G)≤8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture.

关 键 词：total chromatic number planar graph F 5-subgraph 05C40 

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