Polynomial expansion implies bounded twin-width

Informal Conjecture (polynomial expansion and bounded twin-width) · arXiv:2004.14789

arXiv Informal medium confidence— first stated 2021-10-25

Authors: Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant

Status open high confidence

The conjecture that all classes of polynomial expansion have bounded twin-width remains open as of 2026. Bonnet's TWIN-WIDTH ANR JCJC open-questions page explicitly lists this question and remarks 'If this is true, we are quite far from proving it.' No paper resolving or disproving the conjecture has been found in the indexed literature. The closely related question of whether every K_{t,t}-free string-graph class has twin-width bounded by a function of t is also listed as open.

Reviewer notes. Bonnet's open-questions page (https://perso.ens-lyon.fr/edouard.bonnet/openQuestions.html) was verified via WebFetch and confirms the conjecture is still open with the remark 'If this is true, we are quite far from proving it.' No follow-up paper resolving it in either direction was found after four web calls.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. All classes of polynomial expansion may also have bounded twin-width.

Context

The authors note that proper minor-closed classes have bounded twin-width, and observe that bounded twin-width is incomparable with bounded degree, bounded expansion, and nowhere denseness. They remark 'As far as we know, all classes of polynomial expansion may also have bounded twin-width,' suggesting this as an open direction. Figure 3 depicts this with a dash-dotted edge indicating possible inclusion.

Notes. Stated in hedged prose ('as far as we know … may also'); clearly conjectural but no labelled environment.

Source paper

Twin-width I: tractable FO model checking
Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant · 2021-10-25
https://arxiv.org/abs/2004.14789 PDF source