Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P4
EUROCOMB’23
305–313
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.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Linda Cook, Tomáš Masařík, Marcin Pilipczuk, Amadeus Reinald, Uéverton S. Souza