← All problems

Hahn–Hell–Poljak conjecture for odd wheels

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
  1. 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.