The paper demonstrates induced subgraphs and monochromatic edges in graphs with independence number two, suggesting implications for Odd Hadwiger's Conjecture.
A Kₜ-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ₜ minor or an odd clique minor of order t if it contains an odd Kₜ-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 n/2. We then prove that every graph G on n vertices with α(G)≤ 2 contains an odd clique minor of order n/2 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 K₁ + P₄, K₂+(K₁∪ K₃), K₁+(K₁∪ K₄), K₇⁻, K₇, or the kite graph.
No takes yet. Share an insight, caveat, or question.
Ji et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: