Twin-Width and Transductions of Proper k-Mixed-Thin Graphs

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BALABÁN Jakub HLINĚNÝ Petr JEDELSKÝ Jan

Year of publication 2022
Type Article in Proceedings
Conference WG 2022: Graph-Theoretic Concepts in Computer Science
MU Faculty or unit

Faculty of Informatics

Citation
Web
Doi http://dx.doi.org/10.1007/978-3-031-15914-5_4
Keywords twin-width;proper interval graph;proper mixed-thin graph;transduction equivalence
Description The new graph parameter twin-width, recently introduced by Bonnet et al., allows for an FPT algorithm for testing all FO properties of graphs. This makes classes of efficiently bounded twin-width attractive from the algorithmic point of view. In particular, such classes (of small twin-width) include proper interval graphs, and (as digraphs) posets of width k. Inspired by an existing generalization of interval graphs into so-called k-thin graphs, we define a new class of proper k-mixed-thin graphs which largely generalizes proper interval graphs. We prove that proper k-mixed-thin graphs have twin-width linear in k, and that a certain subclass of k-mixed-thin graphs is transduction-equivalent to posets of width ??' such that there is a quadratic relation between k and ??'.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.