Twin-width and logic (Part 1)

We introduce the contraction sequences, which allow to define the twin-width of a graph and more generally the so-called reduced parameters. To form some intuition, we survey which classes have bounded twin-width and which do not. We first recast the proof of the Courcelle-Makowsky-Rotics theorem (on MSO model checking of classes of bounded clique-width) that uses the Feferman-Vaught theorem in the language of component twin-width --a reduced parameter. We then add a Gaifman-like locality argument to get a fixed-parameter tractable algorithm on classes of bounded twin-width, when given a witness of low twin-width. We show that transductions of bounded twin-width classes have bounded twin-width. We survey other connections of twin-width and logic, notably the characterizations that: -a class has bounded twin-width if and only if it is the transduction of a proper permutation class, -a class of totally ordered graphs has bounded twin-width if and only if it is monadically dependent.

Authors

• Edouard Bonnet

Keywords

No keywords are indexed for this paper.