Generalized subdivisions in digraphs spanned by subdivision of smaller digraphs and the chromatic number

Articles in Press

Document Type : Original paper

Author

College of Engineering and Technology, American University of the Middle East, Egaila, 54200, Kuwait

Abstract

A generalized subdivision H′ of a digraph H is obtained by replacing each arc e=(x,y)∈E(H) with tail x and head y, by an oriented path Pe whose first arc has tail x and whose last arc has head y, all these new paths being internally disjoint. If all these new paths are directed ones, then H′ is simply a subdivision of H. The number of blocks (which turns out to have the same parity of |E(H)|) of the generalized subdivision H′ of H is the sum of all the number of blocks of the new paths Pe. In this paper, we prove that if D is spanned by a subdivision of a digraph H such that χ(D) is at least 2n+|V(H)|+|E(H)|, then D contains a generalized subdivision of H with n blocks. This bound is simplified when H is an oriented tree. If H is an oriented cycle, then our results assert a special case of a conjecture of Cohen et al. Moreover, the bound is improved to 2n+1 if H is an oriented cycle with two blocks or H is a directed cycle.

Keywords

Main Subjects

References

[1] D. Al-Mniny and S. Ghazal, Secant edges: a tool for Cohen et al.’s conjectures about subdivisions of oriented cycles and bispindles in hamiltonian digraphs with large chromatic number, Graphs Combin. 41 (2025), no. 1, Article ID: 13. https://doi.org/10.1007/s00373-024-02865-7
[2] J.A. Bondy, Diconnected orientations and a conjecture of las vergnas, J. Lond. Math. Soc. 2 (1976), no. 2, 277–282.
https://doi.org/10.1112/jlms/s2-14.2.277
[3] N. Cohen, F. Havet, W. Lochet, and N. Nisse, Subdivisions of oriented cycles in digraphs with large chromatic number, Cycles with two blocks in k-chromatic digraphs 89 (2018), no. 4, 439–456.  https://doi.org/10.1002/jgt.22360
[4] 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
[5] P. Erdös, Graph theory and probability, Can. J. Math. 11 (1959), 34–38. https://doi.org/10.4153/CJM-1959-003-9
[6] T. Gallai, Theory of Graphs, ch. On directed graphs and circuits, pp. 115–118, Academic Press, New York, 1968.
[7] S. Ghazal and S. Tfaili, On subdivisions of oriented cycles in Hamiltonian digraphs with small chromatic number, Commun. Comb. Optim., In press.  https://doi.org/10.22049/cco.2024.29517.2036
[8] 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
[9] B. Roy, Nombre chromatique et plus longs chemins d’un graphe, Rev. Franç. Inform. Rech. Opér. 1 (1967), no. 5, 129–132.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 06 June 2025

Files

Share

How to cite

Statistics