Paper detail

Decomposing graphs into stable and ordered parts

Connections between structural graph theory and finite model theory recently gained a lot of attention. In this setting, many interesting questions remain on the properties of dependent (NIP) hereditary classes of graphs, in particular related to first-order transductions. In this paper, we study modelizations (which are strong forms of transduction pairings) of classes of graphs by classes of structures. In particular, we consider models obtained by coupling a partial order and a colored graph (thus forming a partially ordered colored graph). Motivated by Simon's decomposition theorem of dependent types into a stable part and a distal (order-like) part, we conjecture that every dependent hereditary class of graphs admits a modelization in a monadically dependent coupling of a class of posets with bounded treewidth cover graphs and a monadically stable class of colored graphs. In this paper, we consider the first non-trivial case (classes with bounded linear cliquewidth) and prove that the conjecture holds in a strong form, the model class being a monadically dependent coupling of a class of disjoint unions of chains and a class of colored graphs with bounded pathwidth. We extend our study to classes that admit bounded-size bounded linear cliquewidth decompositions and prove that they have a modelization in a monadically dependent coupling of a class of disjoint unions of chains and a class of colored graphs with bounded expansion, the model class also admitting bounded-size bounded linear cliquewidth decompositions.