Coloring dense digraphs (Q5919339)

Let \(\alpha (D),\chi (D)\) denote the independence and the chromatic number of a digraph \(D,\) respectively. A tournament \ \(S\) is called a hero, if there is a number \(f(S)\) such that \(\chi (T)\leq f(S)\) for every tournament \(T\) that does not contain \(S\) as an induced subgraph. \textit{E. Berger} et al. [J. Comb. Theory, Ser. B 103, No. 1, 1--20 (2013; Zbl 1254.05064)] fully characterized the class of heroes. In this paper, the authors introduce a notion of a superhero. A digraph \(H\) is called a superhero if for every \(\alpha \geq 1,\) there is a number \(g(H,\alpha )\) such that \(\chi (D)\leq g(H,\alpha )\) for every digraph \(D\), \(\alpha (D)=\alpha ,\) that does not contain \(H\) as an induced subgraph. The main result of the paper states that a digraph is a superhero if and only if it is a hero.