Odd clique minors in graphs with independence number two
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_ | 1866913838029340672 |
|---|---|
| author | Ji, Yuqing Song, Zi-Xia Weiss, Evan Zhang, Xia |
| author_facet | Ji, Yuqing Song, Zi-Xia Weiss, Evan Zhang, Xia |
| contents | A $K_t$-expansion consists of $t$ vertex-disjoint trees, every two of which are joined by an edge. We call such an expansion odd if its vertices can be two-colored so that the edges of the trees are bichromatic but the edges between trees are monochromatic. A graph contains an odd $K_t$ minor or an odd clique minor of order $t$ if it contains an odd $K_t$-expansion. Gerards and Seymour from 1995 conjectured that every graph $G$ contains an odd $K_{χ(G)}$ minor, where $χ(G)$ denotes the chromatic number of $G$. This conjecture is referred to as ``Odd Hadwiger's Conjecture". Let $α(G)$ denote the independence number of a graph $G$. In this paper we investigate the Odd Hadwiger's Conjecture for graphs $G$ with $α(G)\le2$. We first observe that a graph $G$ on $n$ vertices with $α(G)\le2$ contains an odd $K_{χ(G)}$ minor if and only if $G$ contains an odd clique minor of order $\lceil n/2\rceil$. We then prove that every graph $G$ on $n$ vertices with $α(G)\le 2$ contains an odd clique minor of order $\lceil n/2\rceil$ if $G$ contains a clique of order $n/4$ when $n$ is even and $(n+3)/4$ when $n$ is odd, or $G$ does not contain $H$ as an induced subgraph, where $α(H)\le 2$ and $H$ is an induced subgraph of $K_1 + P_4$, $K_2+(K_1\cup K_3)$, $K_1+(K_1\cup K_4)$, $K_7^-$, $K_7$, or the kite graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_07727 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Odd clique minors in graphs with independence number two Ji, Yuqing Song, Zi-Xia Weiss, Evan Zhang, Xia Combinatorics A $K_t$-expansion consists of $t$ vertex-disjoint trees, every two of which are joined by an edge. We call such an expansion odd if its vertices can be two-colored so that the edges of the trees are bichromatic but the edges between trees are monochromatic. A graph contains an odd $K_t$ minor or an odd clique minor of order $t$ if it contains an odd $K_t$-expansion. Gerards and Seymour from 1995 conjectured that every graph $G$ contains an odd $K_{χ(G)}$ minor, where $χ(G)$ denotes the chromatic number of $G$. This conjecture is referred to as ``Odd Hadwiger's Conjecture". Let $α(G)$ denote the independence number of a graph $G$. In this paper we investigate the Odd Hadwiger's Conjecture for graphs $G$ with $α(G)\le2$. We first observe that a graph $G$ on $n$ vertices with $α(G)\le2$ contains an odd $K_{χ(G)}$ minor if and only if $G$ contains an odd clique minor of order $\lceil n/2\rceil$. We then prove that every graph $G$ on $n$ vertices with $α(G)\le 2$ contains an odd clique minor of order $\lceil n/2\rceil$ if $G$ contains a clique of order $n/4$ when $n$ is even and $(n+3)/4$ when $n$ is odd, or $G$ does not contain $H$ as an induced subgraph, where $α(H)\le 2$ and $H$ is an induced subgraph of $K_1 + P_4$, $K_2+(K_1\cup K_3)$, $K_1+(K_1\cup K_4)$, $K_7^-$, $K_7$, or the kite graph. |
| title | Odd clique minors in graphs with independence number two |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2505.07727 |