Bounds for the Vertex Chromatic Number of Connected Triangle-Free Graphs

Abstract

It was recently shown that every connected graph of order $n\ge 5$ and size $m$ satisfies $\chi (G)\le \lceil \frac{m}{\sqrt{n}}\rceil$, and it was asked whether the stronger inequality $\chi (G)\le \lceil \frac{m}{2\sqrt{n}}\rceil +1$ holds for every connected triangle-free graph. In this paper, we answer this question in the affirmative. In fact, we prove that every connected triangle-free graph $G$ with $G\ncong C_5$ satisfies $\chi (G)\le \lceil \frac{m}{\sqrt{5.5n}}\rceil +1$, where the constant $\sqrt{5.5}$ cannot be replaced by any constant greater than or equal to $\sqrt{6}$, and the equality holds for the Grötzsch graph and for every odd cycle of length between $7$ and $21$.