A. Beikmohammadi

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

It was recently shown that every connected graph of order $n \geq 5$ and size $m$ satisfies $\chi(G) \leq \left\lceil \frac{m}{\sqrt{n}} \right\rceil$, and it was asked whether the stronger inequality $\chi(G) \leq \left\lceil \frac{m}{2\sqrt{n}} \right\rceil + 1$ holds for every connected triangle-free graph. In this...