Acyclic subgraphs of tournaments with high chromatic number
Jacob Fox, Matthew Kwan, Benny Sudakov · Bulletin of the London Mathematical Society · 2021
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.