Bounding the chromatic number of tournaments by arc neighborhoods

Felix Klingelhoefer, Alantha Newman

Published 2023-07-10Version 1

The chromatic number of a directed graph is the minimum number of induced acyclic subdigraphs that cover its vertex set, and accordingly, the chromatic number of a tournament is the minimum number of transitive subtournaments that cover its vertex set. The neighborhood of an arc $uv$ in a tournament $T$ is the set of vertices that form a directed triangle with arc $uv$. We show that if the neighborhood of every arc in a tournament has bounded chromatic number, then the whole tournament has bounded chromatic number. We show that this holds more generally for oriented graphs with bounded independence number, which we use to prove the equivalence of a conjecture of El-Zahar and Erd\H{o}s and a recent conjecture of Nguyen, Scott and Seymour relating the structure of graphs and tournaments with high chromatic number.