Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2505.15446 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916749354467328 |
|---|---|
| author | Ayoub, Hiba Zayat, Soukaina Al-Mniny, Darine |
| author_facet | Ayoub, Hiba Zayat, Soukaina Al-Mniny, Darine |
| contents | A cycle C(k1,k2,...,kn) is the oriented cycle formed of n blocks of lengths k1,k2,...,kn-1 and kn respectively. In 2018 Cohen et al. conjectured that for every positive integers k1,k2,...,kn there exists a constant g(k1,k2,...,kn) such that every strongly connected digraph containing no subdivisions of C(k1,k2,...,kn) has a chromatic number at most g(k1,k2,...,kn). In their paper, Cohen et al. confirmed the conjecture for cycles with two blocks and for cycles with four blocks having all its blocks of length 1. Recently, the conjecture was proved for special types of four-blocks cycles. In this paper, we confirm Cohen et al.'s conjecture for all six-blocks cycles C(k,1,1,1,1,1). Precisely, for any integer k, we prove that every strongly connected digraph containing no subdivisions of C(k,1,1,1,1,1) has a chromatic number at most O(k), and we significantly reduce the chromatic number in case k=1. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_15446 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Subdivisions of Six-Blocks Cycles C(k,1,1,1,1,1) in Strong Digraphs Ayoub, Hiba Zayat, Soukaina Al-Mniny, Darine Combinatorics A cycle C(k1,k2,...,kn) is the oriented cycle formed of n blocks of lengths k1,k2,...,kn-1 and kn respectively. In 2018 Cohen et al. conjectured that for every positive integers k1,k2,...,kn there exists a constant g(k1,k2,...,kn) such that every strongly connected digraph containing no subdivisions of C(k1,k2,...,kn) has a chromatic number at most g(k1,k2,...,kn). In their paper, Cohen et al. confirmed the conjecture for cycles with two blocks and for cycles with four blocks having all its blocks of length 1. Recently, the conjecture was proved for special types of four-blocks cycles. In this paper, we confirm Cohen et al.'s conjecture for all six-blocks cycles C(k,1,1,1,1,1). Precisely, for any integer k, we prove that every strongly connected digraph containing no subdivisions of C(k,1,1,1,1,1) has a chromatic number at most O(k), and we significantly reduce the chromatic number in case k=1. |
| title | Subdivisions of Six-Blocks Cycles C(k,1,1,1,1,1) in Strong Digraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2505.15446 |