Deciding twin-width at most 4 is NP-complete

DOI10.4230/LIPICS.ICALP.2022.18MaRDI QIDQ6560802FDOQ6560802

Pierre Bergé, Hugues Déprés, Édouard Bonnet

Publication date: 24 June 2024

zbMATH Keywords

lower boundstwin-width

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cited In (3)

• Planar graph with twin-width seven
• Twin-width of graphs with tree-structured decompositions
• Twin-width and transductions of proper \(k\)-mixed-thin graphs

This page was built for publication: Deciding twin-width at most 4 is NP-complete

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