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

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

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

Rok publikování 2022
Druh Článek ve sborníku
Konference WG 2022: Graph-Theoretic Concepts in Computer Science
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www
Doi http://dx.doi.org/10.1007/978-3-031-15914-5_4
Klíčová slova twin-width;proper interval graph;proper mixed-thin graph;transduction equivalence
Popis 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 ??'.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.