2025/05/12 by Yuqing Ji, Ji, Yuqing, Zi‐Xia Song +4 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2505.07727
openalex publication_date 2025/05/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A Kt-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 Kt minor or an odd clique minor of order t if it contains an odd Kt-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)≤2. We first observe that a graph G on n vertices with α(G)≤2 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)≤ 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)≤ 2 and H is an induced subgraph of K1 + P4, K2+(K1∪ K3), K1+(K1∪ K4), K7-, K7, or the kite graph.