Dominating Hadwiger's Conjecture for graphs $G$ with $α(G)=2$
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909905047257088 |
|---|---|
| author | Scully, Michael Song, Zi-Xia |
| author_facet | Scully, Michael Song, Zi-Xia |
| contents | Hadwiger's Conjecture from 1943 states that every graph with chromatic number $t$ contains a $K_t$ minor. Illingworth and Wood [arXiv:2405.14299] introduced the concept of a ``dominating $K_t$ minor'' and asked whether every graph with chromatic number $t$ contains a dominating $K_t$ minor. This question is a substantial strengthening of Hadwiger's Conjecture. Norin referred to it as the ``Dominating Hadwiger's Conjecture'' and believes it is likely false. In this paper we first observe that a $t$-chromatic $G$ on $n$ vertices with independence number $α(G)\le2$ contains a dominating $K_t$ minor if and only if $G$ contains a dominating $K_{\lceil n/2\rceil}$ minor. Building on this and using a deep result of Chudnovsky and Seymour on packing seagulls, we prove that every graph $G$ on $n$ vertices with $α(G)\le 2$ and $2ω(G)\ge \lceil n/2\rceil+1$ satisfies the Dominating Hadwiger's Conjecture, where $ω(G)$ denotes the clique number of $G$. We further prove that every $H$-free graph $G$ with $α(G)\le 2$ satisfies the Dominating Hadwiger's Conjecture, where $H\in\{2K_1+P_4, K_2+2K_2, K_2+(K_1\cup K_3), K_1+(K_1\cup K_5), W_5^<, W_5^-, W_5, K_7^<, K_7^-, K_7\}$, or $H\ne K_2\cup K_3$ is any graph on at most five vertices such that $α(H)\le2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_12564 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Dominating Hadwiger's Conjecture for graphs $G$ with $α(G)=2$ Scully, Michael Song, Zi-Xia Combinatorics Hadwiger's Conjecture from 1943 states that every graph with chromatic number $t$ contains a $K_t$ minor. Illingworth and Wood [arXiv:2405.14299] introduced the concept of a ``dominating $K_t$ minor'' and asked whether every graph with chromatic number $t$ contains a dominating $K_t$ minor. This question is a substantial strengthening of Hadwiger's Conjecture. Norin referred to it as the ``Dominating Hadwiger's Conjecture'' and believes it is likely false. In this paper we first observe that a $t$-chromatic $G$ on $n$ vertices with independence number $α(G)\le2$ contains a dominating $K_t$ minor if and only if $G$ contains a dominating $K_{\lceil n/2\rceil}$ minor. Building on this and using a deep result of Chudnovsky and Seymour on packing seagulls, we prove that every graph $G$ on $n$ vertices with $α(G)\le 2$ and $2ω(G)\ge \lceil n/2\rceil+1$ satisfies the Dominating Hadwiger's Conjecture, where $ω(G)$ denotes the clique number of $G$. We further prove that every $H$-free graph $G$ with $α(G)\le 2$ satisfies the Dominating Hadwiger's Conjecture, where $H\in\{2K_1+P_4, K_2+2K_2, K_2+(K_1\cup K_3), K_1+(K_1\cup K_5), W_5^<, W_5^-, W_5, K_7^<, K_7^-, K_7\}$, or $H\ne K_2\cup K_3$ is any graph on at most five vertices such that $α(H)\le2$. |
| title | Dominating Hadwiger's Conjecture for graphs $G$ with $α(G)=2$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2510.12564 |