آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 122 |
| تعداد مقالات | 1,551 |
| تعداد مشاهده مقاله | 1,649,917 |
| تعداد دریافت فایل اصل مقاله | 1,543,823 |
Generalized subdivisions in digraphs spanned by subdivision of smaller digraphs and the chromatic number | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 16 خرداد 1404 اصل مقاله (409.21 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2025.29422.1988 | ||
| نویسنده | ||
| Salman Ghazal* | ||
| College of Engineering and Technology, American University of the Middle East, Egaila, 54200, Kuwait | ||
| چکیده | ||
| A generalized subdivision $H'$ of a digraph $H$ is obtained by replacing each arc $e=(x,y)\in E(H)$ with tail $x$ and head $y$, by an oriented path $P_e$ 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 $P_e$. In this paper, we prove that if $D$ is spanned by a subdivision of a digraph $H$ such that $\chi(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. | ||
| کلیدواژهها | ||
| Oriented cycle؛ Hamiltonian؛ Chromatic number؛ Subdivision | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 179 تعداد دریافت فایل اصل مقاله: 128 |
||