Bounding the chromatic number of dense digraphs by arc neighborhoods
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910400661946368 |
|---|---|
| author | Klingelhoefer, Felix Newman, Alantha |
| author_facet | Klingelhoefer, Felix Newman, Alantha |
| contents | The chromatic number of a directed graph is the minimum number of induced acyclic subdigraphs that cover its vertex set, and accordingly, the chromatic number of a tournament is the minimum number of transitive subtournaments that cover its vertex set. The neighborhood of an arc $uv$ in a tournament $T$ is the set of vertices that form a directed triangle with arc $uv$. We show that if the neighborhood of every arc in a tournament has bounded chromatic number, then the whole tournament has bounded chromatic number. This holds more generally for oriented graphs with bounded independence number, and we extend our proof from tournaments to this class of dense digraphs. As an application, we prove the equivalence of a conjecture of El-Zahar and Erdős and a recent conjecture of Nguyen, Scott and Seymour relating the structure of graphs and tournaments with high chromatic number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_04446 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Bounding the chromatic number of dense digraphs by arc neighborhoods Klingelhoefer, Felix Newman, Alantha Combinatorics Discrete Mathematics The chromatic number of a directed graph is the minimum number of induced acyclic subdigraphs that cover its vertex set, and accordingly, the chromatic number of a tournament is the minimum number of transitive subtournaments that cover its vertex set. The neighborhood of an arc $uv$ in a tournament $T$ is the set of vertices that form a directed triangle with arc $uv$. We show that if the neighborhood of every arc in a tournament has bounded chromatic number, then the whole tournament has bounded chromatic number. This holds more generally for oriented graphs with bounded independence number, and we extend our proof from tournaments to this class of dense digraphs. As an application, we prove the equivalence of a conjecture of El-Zahar and Erdős and a recent conjecture of Nguyen, Scott and Seymour relating the structure of graphs and tournaments with high chromatic number. |
| title | Bounding the chromatic number of dense digraphs by arc neighborhoods |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2307.04446 |