Hahn–Hell–Poljak conjecture for odd wheels

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 t1t\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.

Sources & referencesView supporting material

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.