Geodesic
\((\overrightarrow{P_6}\), triangle)-free digraphs have bounded dichromatic number
Pierre Aboulker1 ; Guillaume Aubian2 ; Pierre Charbit3 ; Stéphan Thomassé
1DIENS, École normale supérieure, CNRS, PSL University, Paris, France
2Université de Paris, CNRS, IRIF, Paris, France
3Université de Paris
The electronic journal of combinatorics, Tome 31 (2024) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The dichromatic number of an oriented graph is the minimum size of a partition of its vertices into acyclic induced subdigraphs. We prove that oriented graphs with no induced directed path on six vertices and no triangle have bounded dichromatic number. This is one (small) step towards the general conjecture asserting that for every oriented tree $T$ and every integer $k$, any oriented graph that does not contain an induced copy of $T$ nor a clique of size $k$ has dichromatic number at most some function of $k$ and $T$ .
DOI : 10.37236/11838
Classification : 05C20, 05C15, 05C70
Mots-clés : oriented graphs, locally-out tournaments

Pierre Aboulker  1   ; Guillaume Aubian  2   ; Pierre Charbit  3   ; Stéphan Thomassé 

1 DIENS, École normale supérieure, CNRS, PSL University, Paris, France
2 Université de Paris, CNRS, IRIF, Paris, France
3 Université de Paris 
@article{10_37236_11838,
     author = {Pierre Aboulker and Guillaume Aubian and Pierre Charbit and St\'ephan Thomass\'e},
     title = {\((\overrightarrow{P_6}\), triangle)-free digraphs have bounded dichromatic number},
     journal = {The electronic journal of combinatorics},
     year = {2024},
     volume = {31},
     number = {4},
     doi = {10.37236/11838},
     zbl = {1556.05052},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11838/}
}
TY  - JOUR
AU  - Pierre Aboulker
AU  - Guillaume Aubian
AU  - Pierre Charbit
AU  - Stéphan Thomassé
TI  - \((\overrightarrow{P_6}\), triangle)-free digraphs have bounded dichromatic number
JO  - The electronic journal of combinatorics
PY  - 2024
VL  - 31
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11838/
DO  - 10.37236/11838
ID  - 10_37236_11838
ER  - 
%0 Journal Article
%A Pierre Aboulker
%A Guillaume Aubian
%A Pierre Charbit
%A Stéphan Thomassé
%T \((\overrightarrow{P_6}\), triangle)-free digraphs have bounded dichromatic number
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/11838/
%R 10.37236/11838
%F 10_37236_11838
Pierre Aboulker; Guillaume Aubian; Pierre Charbit; Stéphan Thomassé. \((\overrightarrow{P_6}\), triangle)-free digraphs have bounded dichromatic number. The electronic journal of combinatorics, Tome 31 (2024) no. 4. doi: 10.37236/11838

Cité par Sources :