2018/12/01 by Enqiang Zhu, Zhu, Enqiang, Chanjuan Liu +3
Computer Science · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1812.00133
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, "On the 7 total colorability of planar graphs with maximum degree 6 and without 4-cycles", Graphs and Combinatorics, 25: 401-407, 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 4-cycles or not incident with three cycles of size p,q,ℓ for some \p,q,ℓ\∈ \\3,4,4\,\3,3,4\\.