On subdivisions of oriented cycles in Hamiltonian digraphs with small chromatic number

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics and Physics, Lebanese International University, LIU, Beirut, Lebanon

2 Department of Mathematics and Physics, The International University of Beirut, BIU, Beirut, Lebanon

3 Department of Mathematics, Faculty of Sciences I, Lebanese University, Beirut, Lebanon

Abstract

Cohen et al. conjectured that for each oriented cycle $C$, there is a smallest positive integer $f(C)$ such that every $f(C)$-chromatic strong digraph contains a subdivision of $C$. Let $C$ be an oriented cycle on $n$ vertices. For the class of Hamiltonian digraphs, El Joubbeh proved that $f(C)\leq 3n$. In this paper, we improve El Joubbeh's result by showing that $f(C)\leq 2n$ for the class of Hamiltonian digraphs.

Keywords

Main Subjects

References

[1] L. Addario-Berry, F. Havet, and S. Thomassé, Paths with two blocks in $n$-chromatic digraphs, J. Comb. Theory Ser. B. 97 (2007), no. 4, 620–626.
https://doi.org/10.1016/j.jctb.2006.10.001
[2] S. Bessy and S. Thomassé, Spanning a strong digraph by α circuits: A proof of Gallai’s conjecture, Combinatorica 27 (2007), 659–667.
https://doi.org/10.1007/s00493-007-2073-3
[3] J.A. Bondy, Diconnected orientations and a conjecture of Las Vergnas, J. Lond. Math. Soc. s2-14 (1976), no. 2, 277–282.
https://doi.org/10.1112/jlms/s2-14.2.277
[4] S.A. Burr, Subtrees of directed graphs and hypergraphs, Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing, Boca Raton, Congr. Numer, vol. 28, 1980, pp. 227–239.
5] N. Cohen, F. Havet, W. Lochet, and N. Nisse, Subdivisions of oriented cycles in digraphs with large chromatic number, J. Graph Theory 89 (2018), no. 4, 439–456.
https://doi.org/10.1002/jgt.22360
[6] M. El Joubbeh, Subdivisions of oriented cycles in Hamiltonian digraphs with small chromatic number, Discrete Math. 346 (2023), no. 1, Article ID: 113209.
https://doi.org/10.1016/j.disc.2022.113209
[7] M. El Joubbeh and S. Ghazal, Existence of paths with t blocks in $k(t)$-chromatic, Discrete Appl. Math. 342 (2024), 381–384 .
https://doi.org/10.1016/j.dam.2023.09.025
[8] P. Erd¨os, Graph theory and probability, Canad. J. Math. 11 (1959), 34–38.
https://doi.org/10.4153/CJM-1959-003-9
[9] R. Kim, S.J. Kim, J. Ma, and B. Park, Cycles with two blocks in $k$-chromatic digraphs, J. Graph Theory 88 (2018), no. 4, 592–605.
https://doi.org/10.1002/jgt.22232
[10] D.A. Mniny and S. Ghazal, Remarks on the subdivisions of bispindles and two-blocks cycles in highly chromatic digraphs, arXiv preprint arXiv:2010.10787 (2020).
[11] B. Roy, Nombre chromatique et plus longs chemins d’un graphe, Revue Fran¸caise D’Informatique Et De Recherche Opérationnelle 1 (1967), no. 5, 129–132.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 02 August 2024

Files

Share

How to cite

Statistics