Deciding twin-width at most 4 is NP-complete

DOI10.4230/LIPICS.ICALP.2022.18MaRDI QIDQ6560802FDO

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

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 and transductions of proper \(k\)-mixed-thin graphs
• Twin-width of graphs with tree-structured decompositions

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)