Acyclic subgraphs of tournaments with high chromatic number. Issue 2 (5th January 2021) - Fox, Jacob; Kwan, Matthew; Sudakov, Benny
Abstract: 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.