Bonnet's sparse twin-width 3 conjecture for bounded tree-width

Let C\mathcal{C} be a class of graphs of twin-width at most 33, and suppose there exists an integer tt such that no graph GCG\in\mathcal{C} contains Kt,tK_{t,t} as a subgraph. Sparse twin-width 3 conjecture. Then C\mathcal{C} has bounded tree-width. This conjecture relates sparse graph classes of bounded twin-width to the structural theory of bounded tree-width; the paper proves the analogous statement for twin-width at most 22, while the case of twin-width 33 is presented as the motivating open problem.

Sources & referencesView supporting material

Primary source

Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel, Petr Hliněný, Filip Pokrývka and Marek Sokołowski, “Sparse Graphs of Twin-width 2 Have Bounded Tree-width”, arXiv:2307.01732 (2023).

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.