On total chromatic number of planar graphs without 4-cycles

摘要

Let G be a simple graph with maximum degree Δ(G) and total chromatic number χ_(ve)(G). Vizing conjectured that Δ(G) + 1 ≤ χ_(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 χ_(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.