The induced double-wheel conjecture for K1,dK_{1,d}-free graphs

Let k,dk,d be positive integers. The Cartesian product G\openboxHG\openbox H is the graph with vertex set V(G)×V(H)V(G)\times V(H) in which (u1,v1)(u_1,v_1) and (u2,v2)(u_2,v_2) are adjacent exactly when either u1=u2u_1=u_2 and v1v2E(H)v_1v_2\in E(H), or v1=v2v_1=v_2 and u1u2E(G)u_1u_2\in E(G). A kk-double wheel is C\openboxP2C\openbox P_2, where CC is a cycle on kk vertices. A graph is K1,dK_{1,d}-free if it has no induced K1,dK_{1,d}, and α-tw(G)\operatorname{\alpha\text{-}\mathsf{tw}}(G) denotes its tree-independence number.

Double-wheel conjecture. There exists a function f:N2Nf:\mathbb{N}^2\rightarrow\mathbb{N} such that every K1,dK_{1,d}-free graph GG with α-tw(G)f(k,d)\operatorname{\alpha\text{-}\mathsf{tw}}(G)\geq f(k,d) contains the kk-double wheel as an induced minor.

The double wheel is proposed as an intermediate structure toward a cylindrical induced grid, obtained by closing a ladder into a cycle. The paper notes that proving the conjecture would require new methods, and its status remains open.

Sources & referencesView supporting material

Primary source

Mujin Choi and Sebastian Wiederrecht, “Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars”, arXiv:2509.04026 (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.