TY - JOUR
AB - We prove that every n-vertex tournament G has an acyclic subgraph with chromatic number at least n5/9−o(1), while there exists an n-vertex tournament G whose every acyclic subgraph has chromatic number at most n3/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.
AU - Fox, Jacob
AU - Kwan, Matthew Alan
AU - Sudakov, Benny
ID - 9572
IS - 2
JF - Bulletin of the London Mathematical Society
SN - 0024-6093
TI - Acyclic subgraphs of tournaments with high chromatic number
VL - 53
ER -