Seymour's improvement conjecture for Hadwiger numbers

From papers

Let GG be a finite simple graph, let α(G)\alpha(G) denote its independence number, and let had(G)\operatorname{had}(G) denote its Hadwiger number. Seymour's improvement conjecture. There is a constant ε>0\varepsilon > 0 such that every graph GG with α(G)2\alpha(G) \leqslant 2 satisfies

had(G)(13+ε)V(G).\operatorname{had}(G) \geqslant \left(\frac{1}{3} + \varepsilon\right)|V(G)|.

This would improve the classical V(G)/3|V(G)|/3 lower bound for graphs with independence number 22 and is presented as an open conjecture related to Hadwiger's conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Jung Hon Yip, “Dense Matchings of Linear Size in Graphs with Independence Number 2”, arXiv:2512.01401 (2025).

Solutions 0

No solutions have been posted yet.