A sufficient condition for planar graphs with maximum degree 6 to be totally 8-colorable

DOI10.1016/J.DAM.2017.01.036MaRDI QIDQ2030446zbMATH OpenOpenAlexFDO

Authors Jin Xu, Enqiang Zhu

Publication date 7 June 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.00133

zbMATH Keywords

4-fanplanar graphtotal coloring

Mathematics Subject Classification ID

Vertex degrees (05C07) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Abstract: 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 ($Delta(G)+2$)-coloring, where $Delta(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 $Delta(G)geq9$ or $Delta(G)in7,8$ with some restrictions has a total $(Delta(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,ell$ for some $p,q,ellin3,4,4,3,3,4$.

Recommendations

• A sufficient condition for planar graphs of maximum degree 6 to be totally 7-colorable
• A sufficient condition for planar graphs with maximum degree 8 to be 9-totally colorable
• On the 7 total colorability of planar graphs with maximum degree 6 and without 4-cycles
• Total colorings of planar graphs with maximum degree 6 and without adjacent chordal 6-cycles
• Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable

Cites work

• Graph theory
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• Local condition for planar graphs of maximum degree 6 to be total 8-colorable
• On the total coloring of planar graphs.
• SOME UNSOLVED PROBLEMS IN GRAPH THEORY
• The total chromatic number of any multigraph with maximum degree five is at most seven
• Total colorings of planar graphs without adjacent triangles

Cited in

(9)

• On the 7 total colorability of planar graphs with maximum degree 6 and without 4-cycles
• Total coloring of recursive maximal planar graphs
• A sufficient condition for planar graphs of maximum degree 6 to be totally 7-colorable
• Minimum total coloring of planar graphs with maximum degree 8
• Total coloring of planar graphs with maximum degree 8 and without specified subgraphs
• Total coloring of planar graphs with maximum degree 8
• Local condition for planar graphs of maximum degree 7 to be 8-totally colorable
• Total colorings-a survey
• Local condition for planar graphs of maximum degree 6 to be total 8-colorable

This page was built for publication: A sufficient condition for planar graphs with maximum degree 6 to be totally 8-colorable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2030446)