Conjecture on the largest 3-colourable subgraph of odd-wheel squares

From papers

Let WtW_t be the join of the cycle CtC_t with K1K_1, let α(G)\alpha(G) be the independence number of GG, and let GHG\Box H denote the Cartesian product of graphs. For t2t\geq 2, consider the square W2t+12W_{2t+1}^{\Box 2} and its product with K3K_3. Odd-wheel square subgraph conjecture. For all t2t\geq 2,

(2t+2)α(W2t+1)α(W2t+12K3)=t1.(2t+2)\alpha(W_{2t+1})-\alpha(W_{2t+1}^{\Box 2}\Box K_3)=t-1.

Hence, the largest 33-colourable subgraph of W2t+12W_{2t+1}^{\Box 2} has order 4t2+5t+34t^2+5t+3. This is motivated by computational observations and is presented as a future-work conjecture; no resolution is supplied.

Progress summary

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

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

Solutions 0

No solutions have been posted yet.