Plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles are 3-colorable

2017/02/24 by Ligang Jin, Yingli Kang, Jin, Ligang +5
Computer Science · Mathematics · #05C10 #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1702.07558

openalex publication_date 2017/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Listed as No. 53 among the one hundred famous unsolved problems in [J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, Berlin, 2008] is Steinberg's conjecture, which states that every planar graph without 4- and 5-cycles is 3-colorable. In this paper, we show that plane graphs without 4- and 5-cycles are 3-colorable if they have no ext-triangular 7-cycles. This implies that (1) planar graphs without 4-, 5-, 7-cycles are 3-colorable, and (2) planar graphs without 4-, 5-, 8-cycles are 3-colorable, which cover a number of known results in the literature motivated by Steinberg's conjecture.

Related

• Steinberg's Conjecture is false
• (1,0,0)-colorability of planar graphs without cycles of length 4 or 6
• The proof of Steinberg's three coloring conjecture
• Three coloring via triangle counting
• A relaxation of Steinberg's Conjecture