Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2409.11421 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916399003205632 |
|---|---|
| author | Alhakim, Abbas Joubbeh, Mouhamad El |
| author_facet | Alhakim, Abbas Joubbeh, Mouhamad El |
| contents | Cohen et al. conjectured that for every oriented cycle $C$ there exist an integer $f(C)$ such that every strong $f(C)$-chromatic digraph contains a subdivision of $C$. El Joubbeh confirmed this conjecture for Hamiltonian digraphs. Indeed, he showed that every $3n$-chromatic Hamiltonian digraph contains a subdivision of every oriented cycle of order $n$. In this article, we improve this bound to $2n$. Furthermore, we show that, if $D$ is a digraph containing a Hamiltonian directed path with chromatic number at least $12n-5$, then $D$ contains a subdivision of every oriented cycle of order $n$. Note that a digraph containing a Hamiltonian directed path need not be strongly connected. Thus, our current result provides a deeper understanding of the condition that may be needed to fully solve the conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_11421 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Subdivisions of Oriented Cycles in Digraphs with Hamiltonian directed path Alhakim, Abbas Joubbeh, Mouhamad El Combinatorics Cohen et al. conjectured that for every oriented cycle $C$ there exist an integer $f(C)$ such that every strong $f(C)$-chromatic digraph contains a subdivision of $C$. El Joubbeh confirmed this conjecture for Hamiltonian digraphs. Indeed, he showed that every $3n$-chromatic Hamiltonian digraph contains a subdivision of every oriented cycle of order $n$. In this article, we improve this bound to $2n$. Furthermore, we show that, if $D$ is a digraph containing a Hamiltonian directed path with chromatic number at least $12n-5$, then $D$ contains a subdivision of every oriented cycle of order $n$. Note that a digraph containing a Hamiltonian directed path need not be strongly connected. Thus, our current result provides a deeper understanding of the condition that may be needed to fully solve the conjecture. |
| title | Subdivisions of Oriented Cycles in Digraphs with Hamiltonian directed path |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2409.11421 |