Extension of Gyarfas-Sumner conjecture to digraphs
share
The dichromatic number of a digraph D is the minimum number of colors needed to color its vertices in such a way that each color class induces an acyclic digraph. As it generalizes the notion of the chromatic number of graphs, it has been a recent center of study. In this work we look at possible extensions of Gyárfás-Sumner conjecture. More precisely, we propose as a conjecture a simple characterization of finite sets ℱ of digraphs such that every oriented graph with sufficiently large dichromatic number must contain a member of ℱ as an induce subdigraph. Among notable results, we prove that oriented triangle-free graphs without a directed path of length 3 are 2-colorable. If condition of "triangle-free" is replaced with "K_4-free", then we have an upper bound of 414. We also show that an orientation of complete multipartite graph with no directed triangle is 2-colorable. To prove these results we introduce the notion of nice sets that might be of independent interest.
READ FULL TEXT