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 become the focus of numerous works. In this work we look at possible extensions of the Gyárfás-Sumner conjecture. In particular, we conjecture a simple characterization of sets $\mathcal F$ of three digraphs such that every digraph with sufficiently large dichromatic number must contain a member of $\mathcal F$ as an induced subdigraph. Among notable results, we 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. We also show that an orientation of a 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.
@article{10_37236_9906,
author = {Pierre Aboulker and Pierre Charbit and Reza Naserasr },
title = {Extension of {Gy\'arf\'as-Sumner} conjecture to digraphs},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {2},
doi = {10.37236/9906},
zbl = {1470.05049},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9906/}
}
TY - JOUR
AU - Pierre Aboulker
AU - Pierre Charbit
AU - Reza Naserasr
TI - Extension of Gyárfás-Sumner conjecture to digraphs
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/9906/
DO - 10.37236/9906
ID - 10_37236_9906
ER -
%0 Journal Article
%A Pierre Aboulker
%A Pierre Charbit
%A Reza Naserasr
%T Extension of Gyárfás-Sumner conjecture to digraphs
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/9906/
%R 10.37236/9906
%F 10_37236_9906
Pierre Aboulker; Pierre Charbit; Reza Naserasr . Extension of Gyárfás-Sumner conjecture to digraphs. The electronic journal of combinatorics, Tome 28 (2021) no. 2. doi: 10.37236/9906
