Extremal triangle-free graphs with chromatic number at least four
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915561874653184 |
|---|---|
| author | Ren, Sijie Wang, Jian Wang, Shipeng Yang, Weihua |
| author_facet | Ren, Sijie Wang, Jian Wang, Shipeng Yang, Weihua |
| contents | Let $G$ be an $n$-vertex triangle-free graph. The celebrated Mantel's theorem showed that $e(G)\leq \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)\leq \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\geq 90$, then $e(G)\leq \lfloor\frac{(n-3)^2}{4}\rfloor+5$. The blow-ups of Grötzsch graph shows that this bound is best possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_07486 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Extremal triangle-free graphs with chromatic number at least four Ren, Sijie Wang, Jian Wang, Shipeng Yang, Weihua Combinatorics Let $G$ be an $n$-vertex triangle-free graph. The celebrated Mantel's theorem showed that $e(G)\leq \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)\leq \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\geq 90$, then $e(G)\leq \lfloor\frac{(n-3)^2}{4}\rfloor+5$. The blow-ups of Grötzsch graph shows that this bound is best possible. |
| title | Extremal triangle-free graphs with chromatic number at least four |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2404.07486 |