Coloring of graphs without long odd holes
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916672098533376 |
|---|---|
| author | Chen, Ran Xu, Baogang |
| author_facet | Chen, Ran Xu, Baogang |
| contents | A {\em hole} is an induced cycle of length at least 4, a $k$-hole is a hole of length $k$, and an {\em odd hole} is a hole of odd length. Let $\ell\ge 2$ be an integer. Let ${\cal A}_{\ell}$ be the family of graphs of girth at least $2\ell$ and having no odd holes of length at least $2\ell+3$, let ${\cal B}_{\ell}$ be the triangle-free graphs which have no 5-holes and no odd holes of length at least $2\ell+3$, and let ${\cal G}_{\ell}$ be the family of graphs of girth $2\ell+1$ and have no odd hole of length at least $2\ell+5$. Chudnovsky {\em et al.} \cite{CSS2016} proved that every graph in ${\cal A}_{2}$ is 58000-colorable, and every graph in ${\cal B}_{\ell}$ is $(\ell+1)4^{\ell-1}$-colorable. Lan and liu \cite{LL2023} showed that for $\ell\geq3$, every graph in ${\cal G}_{\ell}$ is 4-colorable. It is not known whether there exists a small constant $c$ such that graphs of ${\cal G}_2$ are $c$-colorable. In this paper, we show that every graph in ${\cal G}_2$ is 1456-colorable, and every graph in ${\cal A}_{3}$ is 4-colorable. We also show that every 7-hole free graph in ${\cal B}_{\ell}$ is $(12\ell+8)$-colorable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_01808 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Coloring of graphs without long odd holes Chen, Ran Xu, Baogang Combinatorics A {\em hole} is an induced cycle of length at least 4, a $k$-hole is a hole of length $k$, and an {\em odd hole} is a hole of odd length. Let $\ell\ge 2$ be an integer. Let ${\cal A}_{\ell}$ be the family of graphs of girth at least $2\ell$ and having no odd holes of length at least $2\ell+3$, let ${\cal B}_{\ell}$ be the triangle-free graphs which have no 5-holes and no odd holes of length at least $2\ell+3$, and let ${\cal G}_{\ell}$ be the family of graphs of girth $2\ell+1$ and have no odd hole of length at least $2\ell+5$. Chudnovsky {\em et al.} \cite{CSS2016} proved that every graph in ${\cal A}_{2}$ is 58000-colorable, and every graph in ${\cal B}_{\ell}$ is $(\ell+1)4^{\ell-1}$-colorable. Lan and liu \cite{LL2023} showed that for $\ell\geq3$, every graph in ${\cal G}_{\ell}$ is 4-colorable. It is not known whether there exists a small constant $c$ such that graphs of ${\cal G}_2$ are $c$-colorable. In this paper, we show that every graph in ${\cal G}_2$ is 1456-colorable, and every graph in ${\cal A}_{3}$ is 4-colorable. We also show that every 7-hole free graph in ${\cal B}_{\ell}$ is $(12\ell+8)$-colorable. |
| title | Coloring of graphs without long odd holes |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2504.01808 |