Acyclic subgraphs with high chromatic number

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)≤n2. This paper provides the first nontrivial lower and upper bounds for g(n). In particular, it is proved that 14n8∕7≤g(n)≤n2−(2−12)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)=Θ(nlogn) whp.