Coloring Dense Digraphs

The chromatic number of a digraph D is the minimum number of acyclic subgraphs covering the vertex set of D. A tournament H is a hero if every H-free tournament T has chromatic number bounded by a function of H. Inspired by the celebrated Erdos-Hajnal conjecture, Berger et al. fully characterized the class of heroes in 2013. We extend this framework to dense digraphs: A digraph H is a superhero if every H-free digraph D has chromatic number bounded by a function of H and alpha(D), the independence number of the underlying graph of D. We prove here that a digraph is a superhero if and only if it is a hero, and hence characterize all superheroes. This answers a question of Aboulker, Charbit and Naserasr.