2022/03/15 by Zachary Hamaker, Hamaker, Zachary, Vincent Vatter +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Combinatorics (math.CO) #Conjecture #Discrete mathematics #Edge coloring #FOS: Mathematics #Geometry #Graph #Graph coloring #Graph power #Limits and Structures in Graph Theory #Line graph #List coloring #Mathematics #Planar graph #Plane (geometry) #math.CO
paper · pdf · doi:10.48550/arxiv.2203.08136
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2022/03/15 · arxiv created 2022/09/10 · arxiv updated 2022/09/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
In the first partial result toward Steinberg's now-disproved three coloring conjecture, Abbott and Zhou used a counting argument to show that every planar graph without cycles of lengths 4 through 11 is 3-colorable. Implicit in their proof is a fact about plane graphs: in any plane graph of minimum degree 3, if no two triangles share an edge, then triangles make up strictly less than 2/3 of the faces. We show how this result, combined with Kostochka and Yancey's resolution of Ore's conjecture for k = 4, implies that every planar graph without cycles of lengths 4 through 8 is 3-colorable.