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

Ghazal, Salman; Tfaili, Sara

doi:10.22049/cco.2024.29517.2036

تعداد نشریات	6
تعداد شماره‌ها	127
تعداد مقالات	1,607
تعداد مشاهده مقاله	1,816,055
تعداد دریافت فایل اصل مقاله	1,686,893

	On subdivisions of oriented cycles in Hamiltonian digraphs with small chromatic number
Communications in Combinatorics and Optimization
مقاله 1، دوره 11، شماره 2، شهریور 2026، صفحه 307-314 اصل مقاله (348.25 K)
نوع مقاله: Original paper
شناسه دیجیتال (DOI): 10.22049/cco.2024.29517.2036
نویسندگان
Salman Ghazal^* ¹^{، 2}^{، 3}؛ Sara Tfaili¹^{، 2}
¹Department of Mathematics and Physics, Lebanese International University, LIU, Beirut, Lebanon
²Department of Mathematics and Physics, The International University of Beirut, BIU, Beirut, Lebanon
³Department of Mathematics, Faculty of Sciences I, Lebanese University, Beirut, Lebanon
چکیده
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.
کلیدواژه‌ها
oriented cycle؛ Hamiltonian؛ chromatic number؛ subdivision

مراجع
[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ös, 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.
آمار تعداد مشاهده مقاله: 531 تعداد دریافت فایل اصل مقاله: 789

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

آمار

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