A Sufficient Condition for Planar Graphs of Maximum Degree 6 to be Totally 7-Colorable

Abstract EN

A total k-coloring of a graph is an assignment of k colors to its vertices and edges such that no two adjacent or incident elements receive the same color.

The total coloring conjecture (TCC) states that every simple graph G has a total ΔG+2-coloring, where ΔG is the maximum degree of G.

This conjecture has been confirmed for planar graphs with maximum degree at least 7 or at most 5, i.e., the only open case of TCC is that of maximum degree 6.

It is known that every planar graph G of ΔG≥9 or ΔG∈7,8 with some restrictions has a total ΔG+1-coloring.

In particular, in (Shen and Wang, 2009), the authors proved that every planar graph with maximum degree 6 and without 4-cycles has a total 7-coloring.

In this paper, we improve this result by showing that every diamond-free and house-free planar graph of maximum degree 6 is totally 7-colorable if every 6-vertex is not incident with two adjacent four cycles or three cycles of size p,q,ℓ for some p,q,ℓ∈3,4,4,3,3,4.