Seymour's improvement conjecture for Hadwiger numbers

About 1 year old · traced to

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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.