Extension of Gyárfás-Sumner conjecture to digraphs - ENS - École normale supérieure Accéder directement au contenu
Article Dans Une Revue The Electronic Journal of Combinatorics Année : 2021

Extension of Gyárfás-Sumner conjecture to digraphs

Résumé

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 F of digraphs such that every oriented graph with sufficiently large dichromatic number must contain a member of F 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.
Fichier principal
Vignette du fichier
DigraphColoringSept2020 (1).pdf (665.4 Ko) Télécharger le fichier
Loading...

Dates et versions

hal-02969880 , version 1 (17-10-2020)

Identifiants

Citer

Pierre Aboulker, Pierre Charbit, Reza Naserasr. Extension of Gyárfás-Sumner conjecture to digraphs. The Electronic Journal of Combinatorics, 2021, ⟨10.37236/9906⟩. ⟨hal-02969880⟩
59 Consultations
61 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More