Every orientation of a 4-chromatic graph has a non-bipartite acyclic subgraph (Q2073290)

Summary: Let \(f(n)\) denote the smallest integer such that every directed graph with chromatic number larger than \(f(n)\) contains an acyclic subgraph with chromatic number larger than \(n\). The problem of bounding this function was introduced by \textit{L. Addario-Berry} et al. [Discrete Math. 313, No. 8, 967--974 (2013; Zbl 1262.05066)], who noted that \(f(n) \leqslant n^2\). The only improvement over this bound was obtained by \textit{S. Nassar} and \textit{R. Yuster} [Eur. J. Comb. 75, 11--18 (2019; Zbl 1400.05088)], who proved that \(f(2)=3\) using a deep theorem of \textit{C. Thomassen} [Combinatorica 21, No. 3, 417--443 (2001; Zbl 1012.05064)]. Yuster asked if this result can be proved using elementary methods. In this short note we provide such a proof.