The two induced cycles conjecture for K1,dK_{1,d}-free graphs

About 1 year old · traced to

Let η,d\eta,d be positive integers. Let GG be a K1,dK_{1,d}-free graph, and let α-tw⁡(G)\operatorname{\alpha\text{-}\mathsf{tw}}(G) denote its tree-independence number. A set SS is a separator between two vertex sets if deleting SS separates them; α(S)\alpha(S) denotes the independence number of the subgraph induced by SS.

Two induced cycles conjecture. There exists a function f:N2→Nf:\mathbb{N}^2\rightarrow\mathbb{N} such that every K1,dK_{1,d}-free graph GG with α-tw⁡(G)≥f(η,d)\operatorname{\alpha\text{-}\mathsf{tw}}(G)\geq f(\eta,d) contains two induced cycles C1,C2C_1,C_2 such that C1C_1 and C2C_2 are non-adjacent, and every separator SS between C1C_1 and C2C_2 satisfies α(S)≥η\alpha(S)\geq\eta.

This conjecture would provide an analogue of the paper's path-and-cycle connectivity result with two induced cycles, potentially supporting the double-wheel program. The paper presents it as a possible next step and gives no resolution.

References

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.