Acyclic subgraphs of tournaments with high chromatic number
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2019
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913369259245568 |
|---|---|
| author | Fox, Jacob Kwan, Matthew Sudakov, Benny |
| author_facet | Fox, Jacob Kwan, Matthew Sudakov, Benny |
| contents | We prove that every $n$-vertex tournament $G$ has an acyclic subgraph with chromatic number at least $n^{5/9-o(1)}$, while there exists an $n$-vertex tournament $G$ whose every acyclic subgraph has chromatic number at most $n^{3/4+o(1)}$. This establishes in a strong form a conjecture of Nassar and Yuster and improves on another result of theirs. Our proof combines probabilistic and spectral techniques together with some additional ideas. In particular, we prove a lemma showing that every tournament with many transitive subtournaments has a large subtournament that is almost transitive. This may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1912_07722 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Acyclic subgraphs of tournaments with high chromatic number Fox, Jacob Kwan, Matthew Sudakov, Benny Combinatorics We prove that every $n$-vertex tournament $G$ has an acyclic subgraph with chromatic number at least $n^{5/9-o(1)}$, while there exists an $n$-vertex tournament $G$ whose every acyclic subgraph has chromatic number at most $n^{3/4+o(1)}$. This establishes in a strong form a conjecture of Nassar and Yuster and improves on another result of theirs. Our proof combines probabilistic and spectral techniques together with some additional ideas. In particular, we prove a lemma showing that every tournament with many transitive subtournaments has a large subtournament that is almost transitive. This may be of independent interest. |
| title | Acyclic subgraphs of tournaments with high chromatic number |
| topic | Combinatorics |
| url | https://arxiv.org/abs/1912.07722 |