Acyclic subgraphs with high chromatic number. (January 2019) - Nassar, Safwat; Yuster, Raphael
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.