آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 123 |
| تعداد مقالات | 1,567 |
| تعداد مشاهده مقاله | 1,692,079 |
| تعداد دریافت فایل اصل مقاله | 1,577,157 |
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* 1، 2، 3؛ Sara Tfaili1، 2 | ||
| 1Department of Mathematics and Physics, Lebanese International University, LIU, Beirut, Lebanon | ||
| 2Department of Mathematics and Physics, The International University of Beirut, BIU, Beirut, Lebanon | ||
| 3Department 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. | ||
|
آمار تعداد مشاهده مقاله: 482 تعداد دریافت فایل اصل مقاله: 722 |
||