Twin-width bound for K_{t,t}-free O_k-free graphs
Open Question: bounded twin-width for sparse $\mathcal{O}_k$-free graphs · arXiv:2206.00594
Status open high confidence
The open question from arXiv:2206.00594 asks whether $\mathcal{O}_k$-free graphs that exclude $K_{t,t}$ as a subgraph have twin-width bounded by a function of $t$ and $k$. The source paper establishes that such graphs have treewidth at most $O_{t,k}(\log n)$, but the twin-width question is explicitly left open. A related result (arXiv:2307.01732) shows the converse direction for twin-width 2: sparse graphs of twin-width at most 2 have bounded treewidth, but this does not imply bounded twin-width for the $\mathcal{O}_k$-free class. No follow-up resolving the question was found in a wide web search through May 2026.
Reviewer notes. No follow-up resolving or disproving the conjecture was found. Paper 2307.01732 ('Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width') is tangentially related but addresses the inverse direction and is restricted to twin-width 2. The conjecture remains open with high confidence as of May 2026.
Context
The paper shows that sparse $\mathcal{O}_k$-free graphs have logarithmic treewidth, but leaves open whether their twin-width is also bounded as a function of $t$ and $k$. The authors note that $\mathcal{O}_2$-free graphs without $K_{3,3}$ already yield a new family of counterexamples to bounded treewidth from forbidden induced subgraphs alone.
Notes. Stated in prose in the introduction without a labelled theorem environment; language is explicit ('we leave as an open question').
Source paper
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
Marthe Bonamy, Édouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, Alexandra Wesolek · 2024-02-16
https://arxiv.org/abs/2206.00594