Extremal triangle-free graphs with chromatic number at least four

2024/04/11 by Sijie Ren, Jian Wang, Ren, Sijie +5 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2404.07486

openalex publication_date 2024/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Cited by

• Strong spectral stabilities for C_2k+1-free graphs
• Spectral extremal problems for non-bipartite graphs without odd cycles

Related

• Sabotage the Mantel Theorem
• On the number of triangles in K₄-free graphs
• On stability of the Erdős-Rademacher Problem
• Maxima of the Q-index of non-bipartite C₃-free graphs
• A note on the number of triangles in graphs without the suspension of a path on four vertices