Odd and even cycle lengths, minimum degree and chromatic number in graphs
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918220935462912 |
|---|---|
| author | Wang, Xiaolin |
| author_facet | Wang, Xiaolin |
| contents | In this paper, we prove similar results for odd and even cycle lengths. Let $L_o(G)$ denote the set of odd cycle lengths of $G$ and $\ell_o(G)$ denote the longest odd cycle length. In 1992, Gyárfás proved that $χ(G)\leq 2|L_o(G)|+2$, and if $w(G)\leq 2|L_o(G)|+1$, then $χ(G)\leq 2|L_o(G)|+1$. We first prove that if $G$ is a 2-connected non-bipartite graph with $δ(G)\geq 2k$, then $|L_o(G)|\geq k$. Moreover, if $|L_o(G)|=k$, then $2|L_o(G)|+1=\ell_o(G)$, and either $K_{2k+1}\subseteq G$ or $χ(G)\leq 2k$. Applying this result, we prove that if $w(G)\leq 2|L_o(G)|$, then $χ(G)\leq 2|L_o(G)|$ for $|L_o(G)|\geq 2$, improving the result of Gyárfás. We also construct a class of graphs with $w(G)=2|L_o(G)|-1$ but $χ(G)=2|L_o(G)|$ for every $|L_o(G)|\geq 2$. Using our result, we give a short proof of a similar result of $χ(G)$ and $\ell_o(G)$ proved by Kenkre and Vishwanathan.
Our second part is about even cycle lengths. Let $L_e(G)$ denote the set of even cycle lengths of $G$ and $\ell_e(G)$ denote the longest even cycle length. In 2004, Mihók and Schiermeyer proved that $χ(G)\leq 2|L_e(G)|+3$, and if $w(G)\leq 2|L_e(G)|+2$, then $χ(G)\leq 2|L_e(G)|+2$. We first prove that if $G$ is a 2-connected graph with $δ(G)\geq 2k+1$, then $|L_e(G)|\geq k$. Moreover, if $|L_e(G)|=k$, then $2|L_e(G)|+2=\ell_e(G)$, and either $K_{2k+2}\subseteq G$ or $χ(G)\leq 2k+1$. Applying this result, we prove that if $w(G)\leq 2|L_e(G)|+1$, then $χ(G)\leq 2|L_e(G)|+1$ for $|L_e(G)|\geq 2$, improving the result of Mihók and Schiermeyer. We also construct a class of graphs with $w(G)=2|L_e(G)|$ but $χ(G)=2|L_e(G)|+1$ for every $|L_e(G)|\geq 2$. Our result can deduce a similar result of $χ(G)$ and $\ell_e(G)$.
The above results also improve some results of consecutive odd or even cycle lengths. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_18961 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Odd and even cycle lengths, minimum degree and chromatic number in graphs Wang, Xiaolin Combinatorics In this paper, we prove similar results for odd and even cycle lengths. Let $L_o(G)$ denote the set of odd cycle lengths of $G$ and $\ell_o(G)$ denote the longest odd cycle length. In 1992, Gyárfás proved that $χ(G)\leq 2|L_o(G)|+2$, and if $w(G)\leq 2|L_o(G)|+1$, then $χ(G)\leq 2|L_o(G)|+1$. We first prove that if $G$ is a 2-connected non-bipartite graph with $δ(G)\geq 2k$, then $|L_o(G)|\geq k$. Moreover, if $|L_o(G)|=k$, then $2|L_o(G)|+1=\ell_o(G)$, and either $K_{2k+1}\subseteq G$ or $χ(G)\leq 2k$. Applying this result, we prove that if $w(G)\leq 2|L_o(G)|$, then $χ(G)\leq 2|L_o(G)|$ for $|L_o(G)|\geq 2$, improving the result of Gyárfás. We also construct a class of graphs with $w(G)=2|L_o(G)|-1$ but $χ(G)=2|L_o(G)|$ for every $|L_o(G)|\geq 2$. Using our result, we give a short proof of a similar result of $χ(G)$ and $\ell_o(G)$ proved by Kenkre and Vishwanathan. Our second part is about even cycle lengths. Let $L_e(G)$ denote the set of even cycle lengths of $G$ and $\ell_e(G)$ denote the longest even cycle length. In 2004, Mihók and Schiermeyer proved that $χ(G)\leq 2|L_e(G)|+3$, and if $w(G)\leq 2|L_e(G)|+2$, then $χ(G)\leq 2|L_e(G)|+2$. We first prove that if $G$ is a 2-connected graph with $δ(G)\geq 2k+1$, then $|L_e(G)|\geq k$. Moreover, if $|L_e(G)|=k$, then $2|L_e(G)|+2=\ell_e(G)$, and either $K_{2k+2}\subseteq G$ or $χ(G)\leq 2k+1$. Applying this result, we prove that if $w(G)\leq 2|L_e(G)|+1$, then $χ(G)\leq 2|L_e(G)|+1$ for $|L_e(G)|\geq 2$, improving the result of Mihók and Schiermeyer. We also construct a class of graphs with $w(G)=2|L_e(G)|$ but $χ(G)=2|L_e(G)|+1$ for every $|L_e(G)|\geq 2$. Our result can deduce a similar result of $χ(G)$ and $\ell_e(G)$. The above results also improve some results of consecutive odd or even cycle lengths. |
| title | Odd and even cycle lengths, minimum degree and chromatic number in graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2511.18961 |