Extension of Gyárfás-Sumner conjecture to digraphs (Q2030749): Difference between revisions

The dichromatic number of a digraph is the minimum number of colors needed to color its vertices in such a way that each color class induces an acyclic digraph [\textit{V. Neumann-Lara}, J. Comb. Theory, Ser. B 33, 265--270 (1982; Zbl 0506.05031)]. On the other hand, Gyárfás and Sumner conjectured that: Given two graphs \(F_1\) and \(F_2\) the class of graphs with no induced \(F_1\) or \(F_2\) has bounded chromatic number if and only if one of \(F_1\); \(F_2\) is a complete graph and the other is a forest (see [\textit{A. Gyárfás}, Zastosow. Mat. 19, No. 3--4, 413--441 (1987; Zbl 0718.05041); \textit{D. P. Sumner}, in: The theory and applications of graphs. Fourth international conference, May 6--9, 1980, Western Michigan University, Kalamazoo, Michigan. New York, NY etc.: John Wiley \& Sons. 557--576 (1981; Zbl 0476.05037)]). In this paper, the authors look for possible extensions of the Gyarfas-Sumner conjecture. In particular, they conjecture a simple characterization of sets \(F\) of three digraphs such that every digraph with suciently large dichromatic number must contain a member of \(F\) as an induced subdigraph. Regarding this, the authors prove that oriented \(K_4\)-free graphs without a directed path of length \(3\) have bounded dichromatic number, where a bound of 414 is provided. They also show that an orientation of a complete multipartite graph with no directed triangle is \(2\)-colorable. To prove these results, the authors introduce the notion of ``nice sets'' that might be of independent interest.