Let G be an n-vertex triangle-free graph. The celebrated Mantel's theorem showed that e(G)≤ ²/4. In 1962, Erd{o}s (together with Gallai), and independently Andr\'{a}sfai, proved that if G is non-bipartite then e(G)≤ (n-1)²/4+1. In this paper, we extend this result and show that if G has chromatic number at least four and n≥ 150, then e(G)≤ (n-3)²/4+5. The blow-up of Gr\"{o}tzsch graph shows that this bound is best possible.
No takes yet. Share an insight, caveat, or question.
Ren et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: