Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P4

EUROCOMB’23

Abstract
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(G)$ has chromatic number at most $f(\omega(G))$. Aboulker, Charbit, and Naserasr [Extension of Gyárfás-Sumner Conjecture to Digraphs; E-JC 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.

Pages:
305–313
References

Pierre Aboulker, Guillaume Aubian, Pierre Charbit, and Stéphan Thomassé. (P6, triangle)-free digraphs have bounded dichromatic number, 2022. URL: https://arxiv.org/abs/2212.02272.

Pierre Aboulker, Nicolas Bousquet, and Rémi de Verclos. Chordal directed graphs are not χ-bounded. The Electronic Journal of Combinatorics, 29(2):17, 2022. doi: 10.37236/11050.
https://doi.org/10.37236/11050

Pierre Aboulker, Pierre Charbit, and Reza Naserasr. Extension of Gyárfás-Sumner conjecture to digraphs. The Electronic Journal of Combinatorics, 28(2):27, 2021. doi:10.37236/9906.
https://doi.org/10.37236/9906

Eli Berger, Krzysztof Choromanski, Maria Chudnovsky, Jacob Fox, Martin Loebl, Alex Scott, Paul Seymour, and Stéphan Thomassé. Tournaments and colouring. Journal of Combinatorial Theory, Series B, 103(1):1-20, 2013. doi:10.1016/j.jctb. 2012.08.003.
https://doi.org/10.1016/j.jctb.2012.08.003

Alvaro Carbonero. On coloring digraphs with forbidden induced subgraphs, 2023. Master's Thesis for University of Waterloo. URL: http://hdl.handle.net/10012/19321.

Alvaro Carbonero, Patrick Hompe, Benjamin Moore, and Sophie Spirkl. Digraphs−with all induced directed cycles of the same length are not →χ -bounded. The Electronic Journal of Combinatorics, 29(4), 2022. doi:10.37236/11179.
https://doi.org/10.37236/11179

Alvaro Carbonero, Patrick Hompe, Benjamin Moore, and Sophie Spirkl. A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number. Journal of Combinatorial Theory, Series B, 158:63-69, 2023. doi:10.1016/j.jctb.2022.09.001.
https://doi.org/10.1016/j.jctb.2022.09.001

Maria Chudnovsky, Alex Scott, and Paul Seymour. Induced subgraphs of graphs with large chromatic number. XI. orientations. European Journal of Combinatorics, 76:53-61, 2019. doi:10.1016/j.ejc.2018.09.003.
https://doi.org/10.1016/j.ejc.2018.09.003

Linda Cook, Tomáš Masařík, Marcin Pilipczuk, Amadeus Reinald, and Uéverton S. Souza. Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P 4 , 2022. URL: https://arxiv.org/abs/2209.06171.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-042

Paul Erdős. Graph theory and probability. Canadian Journal of Mathematics, 11:34-38, 1959. doi:10.4153/CJM-1959-003-9.
https://doi.org/10.4153/CJM-1959-003-9

Paul Erdős. Problems and results in number theory. In Proceedings of the Ninth Manitoba Conference on Numerical Mathematics and Computing, pages 3-21, 1979. URL: https://users.renyi.hu/~p_erdos/1981-21.pdf.

Paul Erdos and Leo Moser. On the representation of directed graphs as unions of orderings. Math. Inst. Hung. Acad. Sci, 9:125-132, 1964.

András Gyárfás. On Ramsey covering-numbers. Infinite and Finite Sets, 2:801-816, 1975. URL: https://users.renyi.hu/~gyarfas/Cikkek/05_Gyarfas_OnRamseyCoveringNumbers.pdf.

András Gyárfás. Problems from the world surrounding perfect graphs. Applicationes Mathematicae, 19(3-4):413-441, 1987. doi:10.4064/am-19-3-4-413-441.
https://doi.org/10.4064/am-19-3-4-413-441

András Gyárfás. Problem 115. Discrete Mathematics, pages 109-110, 1989/1990. URL: https://www.renyi.hu/~gyarfas/Cikkek/46_Gyarfas_Problem115.pdf.

Ararat Harutyunyan and Bojan Mohar. Two results on the digraph chromatic number. Discrete Mathematics, 312(10):1823-1826, 2012. doi:https://doi.org/10.1016/j.disc.2012.01.028.
https://doi.org/10.1016/j.disc.2012.01.028

Henry A. Kierstead and Stephen G. Penrice. Radius two trees specify χ-bounded classes. Journal of Graph Theory, 18(2):119-129, 1994. doi:10.1002/jgt.3190180203.
https://doi.org/10.1002/jgt.3190180203

Henry A. Kierstead and William T. Trotter. Colorful induced subgraphs. Discrete Mathematics, 101(1):165-169, 1992. doi:10.1016/0012-365X(92)90600-K.
https://doi.org/10.1016/0012-365X(92)90600-K

Henry A. Kierstead and Yingxian Zhu. Radius three trees in graphs with large chromatic number. SIAM Journal on Discrete Mathematics, 17(4):571-581, 2004. doi:10.1137/S0895480198339869.
https://doi.org/10.1137/S0895480198339869

Jan Mycielski. Sur le coloriage des graphs. Colloquium Mathematicae, 3(2):161-162, 1955. URL: http://eudml.org/doc/210000.
https://doi.org/10.4064/cm-3-2-161-162

Víctor Neumann-Lara. The dichromatic number of a digraph. Journal of Combinatorial Theory, Series B, 33(3):265-270, 1982. doi:10.1016/0095-8956(82)90046-6.
https://doi.org/10.1016/0095-8956(82)90046-6

Alex Scott and Paul Seymour. Induced subgraphs of graphs with large chromatic number. XIII. New brooms. European Journal of Combinatorics, 84:103024, 2020. doi:10.1016/j.ejc.2019.103024.
https://doi.org/10.1016/j.ejc.2019.103024

Alex Scott and Paul Seymour. A survey of χ-boundedness. Journal of Graph Theory, 95(3):473-504, 2020. doi:https://doi.org/10.1002/jgt.22601.
https://doi.org/10.1002/jgt.22601

Raphael Steiner. On coloring digraphs with forbidden induced subgraphs. Journal of Graph Theory, 103(2):323-339, 2023. doi:10.1002/jgt.22920.
https://doi.org/10.1002/jgt.22920

David P. Sumner. Subtrees of a graph and the chromatic number. In The Theory and Applications of Graphs: Fourth International Conference, May 6-9, 1980, Western Michigan University, Kalamazoo, Michigan. Wiley, New York, 1981.

Alexander A. Zykov. On some properties of linear complexes. Matematicheskii Sbornik Novaya Seriya, 24(66):163-188, 1949. In Russian. English translation in: American Mathematical Society translations 79 (1952). URL: http://mi.mathnet.ru/msb5974.

Metrics

0

Views

0

PDF views