Hahn–Hell–Poljak conjecture for odd wheels

About 1 year old · traced to

Let WtW_t be the join of the cycle CtC_t with K1K_1, and let d4b0(G)d4b0(G) denote the ultimate independence ratio of a graph GG. For odd wheels, d4b0(W2t+1)d4b0(W_{2t+1}) is bounded below by 1/41/4 because d4b0(G)≥1/χ(G)d4b0(G)\geq 1/\chi(G) and χ(W2t+1)=4\chi(W_{2t+1})=4. Hahn–Hell–Poljak's conjecture. For all integers t≥1t\geq 1,

I(W2t+1)=14.\mathscr{I}(W_{2t+1})=\frac{1}{4}.

Determining the ultimate independence ratio of odd wheels is a central open problem in this setting; the 55-wheel is identified as the smallest graph whose ratio is unknown.

References

Primary source

Alexander Clow, Hitesh Kumar and Shivaramakrishna Pragada, “Improved Bounds for the Ultimate Independence Ratio of Odd Wheels”, arXiv:2511.18747 (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.