A density bound for triangle-free 4-critical graphs

2020/12/02 by Benjamin Moore, Moore, Benjamin, Evelyne Smith‐Roberge +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2012.01503

Abstract

We prove that every triangle-free 4-critical graph G satisfies e(G) ≥ (5v(G)+2)/(3). This result gives a unified proof that triangle-free planar graphs are 3-colourable, and that graphs of girth at least five which embed in either the projective plane, torus, or Klein Bottle are 3-colourable, which are results of Grötzsch, Thomassen, and Thomas and Walls. Our result is nearly best possible, as Davies has constructed triangle-free 4-critical graphs G such that e(G) = (5v(G) + 4)/(3). To prove this result, we prove a more general result characterizing sparse 4-critical graphs with few vertex-disjoint triangles.

Related

• On the Minimum Edge-Density of 4-Critical Graphs of Girth Five
• Density of 5/2-critical graphs
• Three-coloring triangle-free graphs on surfaces III. Graphs of girth\n five
• Constructing a Family of 4-Critical Planar Graphs with High Edge-Density
• Sparse 4-critical graphs have low circular chromatic number