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

Asaf Shapira¹

¹Tel Aviv University

The electronic journal of combinatorics, Tome 29 (2022) no. 1

Résumé

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.

Détail

DOI : 10.37236/10727

Classification : 05C15, 05C20
Mots-clés : chromatic number, graph orientation