A density bound for triangle‐free 4‐critical graphs
Benjamin R. Moore, Evelyne Smith‐Roberge · Journal of Graph Theory · 2022
Abstract We prove that every triangle‐free 4‐critical graph satisfies . This result gives a unified proof that triangle‐free planar graphs are 3‐colourable, as well as 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 the best possible, as Davies has constructed triangle‐free 4‐critical graphs such that . To prove this result, we prove a more general result characterizing sparse 4‐critical graphs with few vertex‐disjoint triangles.