Improved Bounds for the Ultimate Independence Ratio of Odd Wheels

The ultimate independence ratio of a graph G is defined as I(G) = limk→∞ α(Gᵏ)|V(G)|ᵏ, where α(Gᵏ) is the independence number of the Cartesian product of k copies of G. For all graphs G, Hahn, Hell, and Poljak (1995) proved that 1/χ(G) ≤ I(G) ≤ 1/ω(G) where $χ(G)$ is the chromatic number, and $ω(G)$ is the clique number of G. So all graphs G with $χ(G) = ω(G)$ satisfy I(G) = 1/χ(G) = 1/ω(G). A construction of Zhu demonstrates that there exists a graph G with 1/χ(G) < I(G) < 1/ω(G), so neither equality holds in general. In response, Hahn, Hell, and Poljak conjectured that all wheel graphs Wₙ satisfy I(Wₙ) = 1/χ(Wₙ). For even wheels W₂ₜ this follows from the fact χ(W₂ₜ) = ω(W₂ₜ) = 3. Odd wheels of length at least $5$ present a more challenging case, since χ(W₂ₜ₊₁) = 4 and ω(W₂ₜ₊₁) = 3. First, we prove that odd wheels of length at least $7$ satisfy I(W₂ₜ₊₁)≤ 4t²+6t/3(2t+2)²<1/3, which provides the best upper bound for large odd wheels. Next, we prove that I(W₅) ≤ 1019/3888, improving an upper bound of Hahn, Hell, and Poljak that I(W₅) ≤ 11/41. Our proofs combine counting arguments, recursive bounds on α(Wᵏ₂ₜ₊₁), and computer-assisted calculation in the W₅ case.