Extremal triangle-free graphs with chromatic number at least four

Abstract

Let $G$ be an $n$-vertex triangle-free graph. The celebrated Mantel's theorem showed that $e(G)\le \lfloor \frac{n^2}{4}\rfloor$. In 1962, Erdős (together with Gallai), and independently Andrásfai, proved that if $G$ is non-bipartite then $e(G)\le \lfloor \frac{(n-1{)}^2}{4}\rfloor +1$. In this paper, we extend this result and show that if $G$ has chromatic number at least four and $n\ge 90$, then $e(G)\le \lfloor \frac{(n-3{)}^2}{4}\rfloor +5$. The blow-ups of Grötzsch graph shows that this bound is best possible.

14 pages, 4 figures, the proof is slightly improved