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

生成讲解博客的中文版本

生成AI智能校验的中文版本