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

Varování

Publikace nespadá pod Pedagogickou 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í 2024
Druh Článek v odborném periodiku
Časopis / Zdroj DISCRETE MATHEMATICS
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www https://arxiv.org/abs/2202.12536
Doi http://dx.doi.org/10.1016/j.disc.2024.113876
Klíčová slova twin-width;proper interval graph;proper mixed-thin graph;transduction equivalence
Popis The new graph parameter twin-width, introduced by Bonnet, Kim, Thomassé and Watrigant in 2020, 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, classes of efficiently bounded 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 slight subclass of k-mixed-thin graphs is transduction-equivalent to posets of width such that there is a quadratic-polynomial relation between k and . In addition to that, we also give an abstract overview of the so-called red potential method which we use to prove our twin-width bounds.
Související projekty:

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