Acyclic subgraphs of tournaments with high chromatic number

Fox J, Kwan MA, Sudakov B. 2021. Acyclic subgraphs of tournaments with high chromatic number. Bulletin of the London Mathematical Society. 53(2), 619–630.


Journal Article | Published | English

Scopus indexed
Author
Fox, Jacob; Kwan, Matthew AlanIST Austria; Sudakov, Benny
Abstract
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.
Publishing Year
Date Published
2021-04-03
Journal Title
Bulletin of the London Mathematical Society
Volume
53
Issue
2
Page
619-630
ISSN
eISSN
IST-REx-ID

Cite this

Fox J, Kwan MA, Sudakov B. Acyclic subgraphs of tournaments with high chromatic number. Bulletin of the London Mathematical Society. 2021;53(2):619-630. doi:10.1112/blms.12446
Fox, J., Kwan, M. A., & Sudakov, B. (2021). Acyclic subgraphs of tournaments with high chromatic number. Bulletin of the London Mathematical Society. Wiley. https://doi.org/10.1112/blms.12446
Fox, Jacob, Matthew Alan Kwan, and Benny Sudakov. “Acyclic Subgraphs of Tournaments with High Chromatic Number.” Bulletin of the London Mathematical Society. Wiley, 2021. https://doi.org/10.1112/blms.12446.
J. Fox, M. A. Kwan, and B. Sudakov, “Acyclic subgraphs of tournaments with high chromatic number,” Bulletin of the London Mathematical Society, vol. 53, no. 2. Wiley, pp. 619–630, 2021.
Fox J, Kwan MA, Sudakov B. 2021. Acyclic subgraphs of tournaments with high chromatic number. Bulletin of the London Mathematical Society. 53(2), 619–630.
Fox, Jacob, et al. “Acyclic Subgraphs of Tournaments with High Chromatic Number.” Bulletin of the London Mathematical Society, vol. 53, no. 2, Wiley, 2021, pp. 619–30, doi:10.1112/blms.12446.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1912.07722

Search this title in

Google Scholar