Geodesic
Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of \(P_4\)
Linda Cook1 ; Tomáš Masařík2 ; Marcin Pilipczuk2 ; Amadeus Reinald3 ; Uéverton S. Souza4
1Institute for Basic Science, Daejeon
2University of Warsaw
3École Normale Supérieure de Lyon and Institute for Basic Science, Daejeon, Republic of Korea and 4Université Côte d’Azur, Inria, CNRS, I3S, Sophia Antipolis
4University of Warsaw and Instituto de Computação, Universidade Federal Fluminense, Niterói
The electronic journal of combinatorics, Tome 30 (2023) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph $D$ is $H$-free if $D$ does not contain $H$ as an induced sub(di)graph. The Gyárfás-Sumner conjecture is a widely-open conjecture on simple graphs, which states that for any forest $F$, there is some function $f$ such that every $F$-free graph $G$ with clique number $\omega(D)$ has chromatic number at most $f(\omega(D))$. Aboulker, Charbit, and Naserasr [Extension of Gyárfás-Sumner Conjecture to Digraphs, Electron. J. Comb., 2021] proposed an analogue of this conjecture to the dichromatic number of oriented graphs. The dichromatic number of a digraph $D$ is the minimum number of colors required to color the vertex set of $D$ so that no directed cycle in $D$ is monochromatic. Aboulker, Charbit, and Naserasr’s $\overrightarrow{\chi}$ -boundedness conjecture states that for every oriented forest $F$, there is some function f such that every $F$-free oriented graph $D$ has dichromatic number at most $f(\omega(D))$, where $\omega(D)$ is the size of a maximum clique in the graph underlying $D$. In this paper, we perform the first step towards proving Aboulker, Charbit, and Naserasr’s $\overrightarrow{\chi}$-boundedness conjecture by showing that it holds when $F$ is any orientation of a path on four vertices.
DOI : 10.37236/11538
Classification : 05C20, 05C15
Mots-clés : Gyárfás-Sumner conjecture, dichromatic number

Linda Cook  1   ; Tomáš Masařík  2   ; Marcin Pilipczuk  2   ; Amadeus Reinald  3   ; Uéverton S. Souza  4

1 Institute for Basic Science, Daejeon
2 University of Warsaw
3 École Normale Supérieure de Lyon and Institute for Basic Science, Daejeon, Republic of Korea and 4Université Côte d’Azur, Inria, CNRS, I3S, Sophia Antipolis
4 University of Warsaw and Instituto de Computação, Universidade Federal Fluminense, Niterói 
@article{10_37236_11538,
     author = {Linda Cook and Tom\'a\v{s} Masa\v{r}{\'\i}k and Marcin Pilipczuk and Amadeus Reinald and U\'everton S. Souza},
     title = {Proving a directed analogue of the {Gy\'arf\'as-Sumner} conjecture for orientations of {\(P_4\)}},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {3},
     doi = {10.37236/11538},
     zbl = {1533.05102},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11538/}
}
TY  - JOUR
AU  - Linda Cook
AU  - Tomáš Masařík
AU  - Marcin Pilipczuk
AU  - Amadeus Reinald
AU  - Uéverton S. Souza
TI  - Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of \(P_4\)
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11538/
DO  - 10.37236/11538
ID  - 10_37236_11538
ER  - 
%0 Journal Article
%A Linda Cook
%A Tomáš Masařík
%A Marcin Pilipczuk
%A Amadeus Reinald
%A Uéverton S. Souza
%T Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of \(P_4\)
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/11538/
%R 10.37236/11538
%F 10_37236_11538
Linda Cook; Tomáš Masařík; Marcin Pilipczuk; Amadeus Reinald; Uéverton S. Souza. Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of \(P_4\). The electronic journal of combinatorics, Tome 30 (2023) no. 3. doi: 10.37236/11538

Cité par Sources :