Twin-width and transductions of proper k-mixed-thin graphs

DOI10.1016/J.DISC.2024.113876MaRDI QIDQ6552597zbMATH OpenFDO

Authors Jakub Balabán, Petr Hliněný, J. Jedelsky

Publication date 10 June 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DISC.2024.113876

zbMATH Keywords

proper interval graphproper mixed-thin graphred potential methodtransduction equivalencetwin-width

Mathematics Subject Classification ID

Graph theory (05Cxx) Theory of computing (68Qxx) Algorithms in computer science (68Wxx)

Cites work

• Deciding twin-width at most 4 is NP-complete
• scientific article; zbMATH DE number 7638379 (Why is no real title available?)
• scientific article; zbMATH DE number 7803584 (Why is no real title available?)
• On the thinness and proper thinness of a graph
• The stable set problem and the thinness of a graph
• Twin-width IV: ordered graphs and matrices
• Twin-width. I: Tractable FO model checking
• Twin-width. II: Small classes
• Twin-width. VI: The lens of contraction sequences

Cited in

(4)

• Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
• On the thinness of trees
• Improved bounds for twin-width parameter variants with algorithmic applications to counting graph colorings
• Non-crossing H-graphs: a generalization of proper interval graphs admitting FPT algorithms

This page was built for publication: Twin-width and transductions of proper \(k\)-mixed-thin graphs

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