A density bound for triangle-free $4$-critical graphs

Abstract

We prove that every triangle-free $4$-critical graph $G$ satisfies $e(G)\ge \frac{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)=\frac{5v(G)+4}{3}$. To prove this result, we prove a more general result characterizing sparse $4$-critical graphs with few vertex-disjoint triangles.

40 pages. Final version, the authors are thankful for the comments of the referees