Strong Brandt-Thomassé Theorems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914835387645952 |
|---|---|
| author | Łuczak, Tomasz Polcyn, Joanna Reiher, Christian |
| author_facet | Łuczak, Tomasz Polcyn, Joanna Reiher, Christian |
| contents | Solving a long standing conjecture of Erdős and Simonovits, Brandt and Thomassé proved that the chromatic number of each triangle-free graph $G$ such that $δ(G)>|V(G)|/3$ is at most four. In fact, they showed the much stronger result that every maximal triangle-free graph $G$ satisfying this minimum degree condition is a blow-up of either an Andrásfai or a Vega graph.
Here we establish the same structural conclusion on $G$ under the weaker assumption that for $m\in\{2, 3, 4\}$ every sequence of $3m$ vertices has a subsequence of length $m+1$ with a common neighbour. In forthcoming work this will be used to solve an old problem of Andrásfai in Ramsey-Turán theory. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_10745 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Strong Brandt-Thomassé Theorems Łuczak, Tomasz Polcyn, Joanna Reiher, Christian Combinatorics 05C35, 05C07, 05C15 Solving a long standing conjecture of Erdős and Simonovits, Brandt and Thomassé proved that the chromatic number of each triangle-free graph $G$ such that $δ(G)>|V(G)|/3$ is at most four. In fact, they showed the much stronger result that every maximal triangle-free graph $G$ satisfying this minimum degree condition is a blow-up of either an Andrásfai or a Vega graph. Here we establish the same structural conclusion on $G$ under the weaker assumption that for $m\in\{2, 3, 4\}$ every sequence of $3m$ vertices has a subsequence of length $m+1$ with a common neighbour. In forthcoming work this will be used to solve an old problem of Andrásfai in Ramsey-Turán theory. |
| title | Strong Brandt-Thomassé Theorems |
| topic | Combinatorics 05C35, 05C07, 05C15 |
| url | https://arxiv.org/abs/2406.10745 |