Independence number lower bound in K_{t+1}-minor-free graphs

Conjecture 1 · arXiv:1907.12999

arXiv Conjecture high confidence— first stated 2019-07-30

Authors: Zdeněk Dvořák, Liana Yepremyan

Status open high confidence

The conjecture that every n-vertex K_{t+1}-minor-free graph has independence number at least n/t remains open. The source paper itself proves a weaker result restricted to triangle-free graphs (independence number at least n/t^{1-ε} for all sufficiently large t), while the best known general bound without the triangle-free restriction is the Duchet–Meyniel bound α(G) ≥ n/(2t−1) from 1982. Recent breakthroughs on Hadwiger-type coloring (Norin–Postle–Song, Delcourt–Postle giving O(t log log t)-colorability) do not suffice to resolve this independence number conjecture, and no paper proving or disproving the full statement was found.

Reviewer notes. The conjecture is a well-known weakening of Hadwiger's conjecture: Hadwiger would imply chromatic number ≤ t for K_{t+1}-minor-free graphs and thus α(G) ≥ n/t, but the conjecture may be provable independently. The best unconditional general bound remains Duchet–Meyniel (α ≥ n/(2t−1)). A related paper arXiv:2002.11100 extends the Dvořák–Yepremyan triangle-free result to arbitrary H-free graphs (clique minors given independence number), but this is a different direction and does not resolve Conjecture 1. No follow-up paper resolving the full conjecture was found in the indexed literature.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For every positive integer $t$, if an $n$-vertex graph $G$ does not contain $K_{t+1}$ as a minor then $\alpha(G) \geq n/t$.

Context

This conjecture is a natural weakening of Hadwiger's conjecture: since Hadwiger's conjecture would imply every $n$-vertex $K_{t+1}$-minor-free graph has chromatic number at most $t$ and thus an independent set of size at least $n/t$, this bound has attracted considerable attention (see Seymour's survey [31]). Duchet and Meyniel proved the bound holds within a factor of 2 in 1982, and subsequent improvements have been made by Fox, Balogh–Kostochka, and others. The present paper studies this conjecture restricted to triangle-free graphs.

Notes. No explicit attribution appears in the conjecture header; the paper describes it as having 'received quite a lot of attention' and directs the reader to Seymour's survey [31], indicating it is a community/folklore conjecture rather than one originated by the paper authors. Classified as 'states' per the no-attribution-in-header rule.

Source paper

Independence number in triangle-free graphs avoiding a minor
Zdeněk Dvořák, Liana Yepremyan · 2019-07-30
https://arxiv.org/abs/1907.12999 PDF source