Bonnet's sparse twin-width 3 conjecture for bounded tree-width
Bonnet's sparse twin-width 3 conjecture for bounded tree-width
Let be a class of graphs of twin-width at most , and suppose there exists an integer such that no graph contains as a subgraph. Sparse twin-width 3 conjecture. Then 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 , while the case of twin-width 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.