Can I read Acyclic Subgraphs of Tournaments with High Chromatic Number on EtoBox?

Acyclic Subgraphs of Tournaments with High Chromatic Number by Fox, Jacob; Kwan, Matthew; Sudakov, Benny is a scholarly article available to read on EtoBox.

What is Acyclic Subgraphs of Tournaments with High Chromatic Number about?

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.

Author

Fox, Jacob; Kwan, Matthew; Sudakov, Benny

Published

2019

Language

EN