Acyclic subgraphs with high chromatic number. (January 2019)

• Record Type: Journal Article
• Authors: Nassar, Safwat; Yuster, Raphael
• Is Part Of: European journal of combinatorics. Volume 75(2019)
• Page Start: 11
• Page End: 18
• Publication Date: 2019-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2018.07.016
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: For an oriented graph G, let f ( G ) denote the maximum chromatic number of an acyclic subgraph of G . Let f ( n ) be the smallest integer such that every oriented graph G with chromatic number larger than f ( n ) has f ( G ) > n . Let g ( n ) be the smallest integer such that every tournament G with more than g ( n ) vertices has f ( G ) > n . It is straightforward that Ω ( n ) ≤ g ( n ) ≤ f ( n ) ≤ n 2 . This paper provides the first nontrivial lower and upper bounds for g ( n ) . In particular, it is proved that 1 4 n 8 ∕ 7 ≤ g ( n ) ≤ n 2 − ( 2 − 1 2 ) n + 2 . It is also shown that f ( 2 ) = 3, i.e. every orientation of a 4-chromatic graph has a 3-chromatic acyclic subgraph. Finally, it is shown that a random tournament G with n vertices has f ( G ) = Θ ( n log n ) whp.