Odd Hadwiger's conjecture for the complements of Kneser graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910945318535168 |
|---|---|
| author | Chen, Meirun Naserasr, Reza Wang, Lujia Zhou, Sanming |
| author_facet | Chen, Meirun Naserasr, Reza Wang, Lujia Zhou, Sanming |
| contents | A generalization of the four-color theorem, Hadwiger's conjecture is considered as one of the most important and challenging problems in graph theory, and odd Hadwiger's conjecture is a strengthening of Hadwiger's conjecture by way of signed graphs. In this paper, we prove that odd Hadwiger's conjecture is true for the complements $\overline{K}(n,k)$ of the Kneser graphs $K(n,k)$, where $n\geq 2k \ge 4$. This improves a result of G. Xu and S. Zhou (2017) which states that Hadwiger's conjecture is true for this family of graphs. Moreover, we prove that $\overline{K}(n,k)$ contains a 1-shallow complete minor of a special type with order no less than the chromatic number $χ(\overline{K}(n,k))$, and in the case when $7 \le 2k+1 \le n \le 3k-1$ the gap between the odd Hadwiger number and chromatic number of $\overline{K}(n,k)$ is $Ω(1.5^{k})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_10097 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Odd Hadwiger's conjecture for the complements of Kneser graphs Chen, Meirun Naserasr, Reza Wang, Lujia Zhou, Sanming Combinatorics 05C15, 05C22, 05C83 A generalization of the four-color theorem, Hadwiger's conjecture is considered as one of the most important and challenging problems in graph theory, and odd Hadwiger's conjecture is a strengthening of Hadwiger's conjecture by way of signed graphs. In this paper, we prove that odd Hadwiger's conjecture is true for the complements $\overline{K}(n,k)$ of the Kneser graphs $K(n,k)$, where $n\geq 2k \ge 4$. This improves a result of G. Xu and S. Zhou (2017) which states that Hadwiger's conjecture is true for this family of graphs. Moreover, we prove that $\overline{K}(n,k)$ contains a 1-shallow complete minor of a special type with order no less than the chromatic number $χ(\overline{K}(n,k))$, and in the case when $7 \le 2k+1 \le n \le 3k-1$ the gap between the odd Hadwiger number and chromatic number of $\overline{K}(n,k)$ is $Ω(1.5^{k})$. |
| title | Odd Hadwiger's conjecture for the complements of Kneser graphs |
| topic | Combinatorics 05C15, 05C22, 05C83 |
| url | https://arxiv.org/abs/2505.10097 |