Acyclic subgraphs of tournaments with high chromatic number. Issue 2 (5th January 2021)

• Record Type: Journal Article
• Authors: Fox, Jacob; Kwan, Matthew; Sudakov, Benny
• Is Part Of: Bulletin of the London Mathematical Society. Volume 53:Issue 2(2021)
• Page Start: 619
• Page End: 630
• Publication Date: 2021-01-05
• Subjects: 05C15 -- 05C20 -- 05D40 (primary); Mathematics -- Periodicals; 510
• DOI: 10.1112/blms.12446
• Languages: English
• ISSNs: 0024-6093

Abstract

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.