Every Orientation of a $4$-Chromatic Graph has a Non-Bipartite Acyclic Subgraph

Abstract

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 Addario-Berry et al., who noted that $f(n) \leqslant n^2$. The only improvement over this bound was obtained by Nassar and Yuster, who proved that $f(2)=3$ using a deep theorem of Thomassen. Yuster asked if this result can be proved using elementary methods. In this short note we provide such a proof.