Twin-width VIIIa: Delineation

We introduce the notion of delineation. A graph class C is said delineated by twin-width (or simply, delineated ) if for every hereditary closure D of a subclass of C, it holds that D has bounded twin-width if and only if D is monadically dependent. An effective strengthening of delineation for a class C implies that tractable FO model checking on C is perfectly understood: On hereditary closures D of subclasses of C, FO model checking is fixed-parameter tractable (FPT) exactly when D has bounded twin-width. Ordered graphs [BGOdMSTT, STOC ’22], permutation graphs [BKTW, JACM ’22] and tournaments [GT, European Journal of Combinatorics ’25] are effectively delineated, while subcubic graphs are not. On the one hand, we prove that interval graphs, and even, directed path graphs with boundedly many roots are delineated. On the other hand, we observe or show that segment graphs, directed path graphs (with arbitrarily many roots), and visibility graphs of simple polygons are not delineated.

DDC Class

510: Mathematics

Lizenz

https://creativecommons.org/licenses/by/4.0/

Publication version

publishedVersion

Name

1-s2.0-S0195669826000983-main.pdf

Type

Main Article

Size

1.11 MB

Format

Adobe PDF

Options

Twin-width VIIIa: Delineation