论文标题
无三角形的密度限制$ 4 $ - 临界图
A density bound for triangle-free $4$-critical graphs
论文作者
论文摘要
我们证明，每个三角形$ 4 $ - 临界图$ g $满足$ e（g）\ geq \ frac {5v（g）+2} {3} $。该结果提供了一个统一的证据，表明无三角形的平面图为$ 3 $ - 彩色，并且围绕着镶嵌在投射平面，圆环或klein瓶中的围栏的图形至少五个，是$ 3 $ - 颜色的，这是Grötzsch，Thomassen，Thomassen以及Thomas和Thomas和Thomas和Thomas和Walls的结果。我们的结果几乎是最好的，因为戴维斯已经构建了三角形$ 4 $ - 临界图$ g $，因此$ e（g）= \ frac {5v（g） + 4} {3} $。为了证明这一结果，我们证明了一个更一般的结果，表征了稀疏$ 4 $ - 临界图，几乎没有顶点 - 偶有三角形。
We prove that every triangle-free $4$-critical graph $G$ satisfies $e(G) \geq \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.
