Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2409.03407 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916543039799296 |
|---|---|
| author | Yan, Zilong Peng, Yuejian Yuan, Xiaoli |
| author_facet | Yan, Zilong Peng, Yuejian Yuan, Xiaoli |
| contents | Erdős and Simonovits asked the following question: For an integer $c\geq 2$ and a family of non-bipartite graphs $\mathcal{F}$, what is the infimum of $α$ such that any $\mathcal{F}$-free $n$-vertex graph with $n$ large enough and minimum degree at least $αn$ has chromatic number at most $c$? Denote the infimum as $δ_χ(\mathcal{F}, c)$. A fundamental result of Erdős, Stone and Simonovits implies that if $3\le r+1=χ(\mathcal{F})=\min\{χ(F): F\in \mathcal{F}\}$, then for any $c\le r-1$, $δ_χ(\mathcal{F}, c)=1-{1 \over r}$. So the remaining challenge is to determine $δ_χ(\mathcal{F}, c)$ for $c\ge χ(\mathcal{F})-1$. Most previous known results are under the condition that $c= χ(\mathcal{F})-1$. When $c\ge χ(\mathcal{F})$, the only known exact results are $δ_χ(K_3, 3)$ by Häggkvist and Jin, and $δ_χ(K_3, c)$ for every $c\ge4$ by Brandt and Thomassé, $δ_χ(K_r, r)$ and $δ_χ(K_r, r+1)$ by Goddard and Lyle, and Nikiforov. Combining results of Thomassen and Ma, $Ω\bigg((c+1)^{-8(k+1)}\bigg)=δ_χ(C_{2k+1}, c)=O(\frac{k}{c})$ for $c\ge 3$. In this paper, we determine $δ_χ(C_{2k+1}, c)$ for all $c\ge 2$ and $k\ge 3c+4$. We also obtain the following corollary. If $G$ is a graph on $n$ vertices with $c\ge 3$, $χ(G)>c$ and $δ(G)> {n \over 2c+2}$, then $C_{2k+1} \subset G$ for all $k\in [3c+4, {n \over 108(c+1)^c}]$. Methods to obtain all previous known results related to odd cycles cannot be applied to solve for $δ_χ(C_{2k+1}, c)$ for $c\ge 3$.The innovation of our proof is to give the concept of a `strong $2k$-core'. We think that this concept grasps the essence of the problem and it makes our proof concise and elementary (we do not need to borrow any other tools). How to define a proper `core' might be a key to this type of questions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_03407 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Chromatic profiles of odd cycles Yan, Zilong Peng, Yuejian Yuan, Xiaoli Combinatorics Erdős and Simonovits asked the following question: For an integer $c\geq 2$ and a family of non-bipartite graphs $\mathcal{F}$, what is the infimum of $α$ such that any $\mathcal{F}$-free $n$-vertex graph with $n$ large enough and minimum degree at least $αn$ has chromatic number at most $c$? Denote the infimum as $δ_χ(\mathcal{F}, c)$. A fundamental result of Erdős, Stone and Simonovits implies that if $3\le r+1=χ(\mathcal{F})=\min\{χ(F): F\in \mathcal{F}\}$, then for any $c\le r-1$, $δ_χ(\mathcal{F}, c)=1-{1 \over r}$. So the remaining challenge is to determine $δ_χ(\mathcal{F}, c)$ for $c\ge χ(\mathcal{F})-1$. Most previous known results are under the condition that $c= χ(\mathcal{F})-1$. When $c\ge χ(\mathcal{F})$, the only known exact results are $δ_χ(K_3, 3)$ by Häggkvist and Jin, and $δ_χ(K_3, c)$ for every $c\ge4$ by Brandt and Thomassé, $δ_χ(K_r, r)$ and $δ_χ(K_r, r+1)$ by Goddard and Lyle, and Nikiforov. Combining results of Thomassen and Ma, $Ω\bigg((c+1)^{-8(k+1)}\bigg)=δ_χ(C_{2k+1}, c)=O(\frac{k}{c})$ for $c\ge 3$. In this paper, we determine $δ_χ(C_{2k+1}, c)$ for all $c\ge 2$ and $k\ge 3c+4$. We also obtain the following corollary. If $G$ is a graph on $n$ vertices with $c\ge 3$, $χ(G)>c$ and $δ(G)> {n \over 2c+2}$, then $C_{2k+1} \subset G$ for all $k\in [3c+4, {n \over 108(c+1)^c}]$. Methods to obtain all previous known results related to odd cycles cannot be applied to solve for $δ_χ(C_{2k+1}, c)$ for $c\ge 3$.The innovation of our proof is to give the concept of a `strong $2k$-core'. We think that this concept grasps the essence of the problem and it makes our proof concise and elementary (we do not need to borrow any other tools). How to define a proper `core' might be a key to this type of questions. |
| title | Chromatic profiles of odd cycles |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2409.03407 |