Sparse graphs of twin-width 2 have bounded tree-width

DOI10.4230/LIPICS.ISAAC.2023.11MaRDI QIDQ6953210zbMATH OpenFDO

Authors Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel, Petr Hliněný, Filip Pokrývka, Marek Sokołowski

Publication date 24 July 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2023.11

zbMATH Keywords

sparsitytree-widthtwin-widthexcluded grid

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• scientific article; zbMATH DE number 7788458 (Why is no real title available?)
• scientific article; zbMATH DE number 7803584 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Compact representation for matrices of bounded twin-width
• Deciding twin-width at most 4 is NP-complete
• FO model checking on geometric graphs
• Graph minors. II. Algorithmic aspects of tree-width
• On the Boolean-width of a graph: structure and applications
• On the clique-width of some perfect graph classes
• Stable graphs of bounded twin-width
• Towards tight(er) bounds for the excluded grid theorem
• Twin-width IV: ordered graphs and matrices
• Twin-width and generalized coloring numbers
• Twin-width and polynomial kernels
• Twin-width and transductions of proper k-mixed-thin graphs
• Twin-width and types
• Twin-width. I: Tractable FO model checking
• Twin-width. I: Tractable FO model checking
• Twin-width. II: Small classes
• Twin-width. VI: The lens of contraction sequences
• Twin-width. VIII: Delineation and win-wins

This page was built for publication: Sparse graphs of twin-width 2 have bounded tree-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6953210)