A trigraph is a vertex set together with two disjoint edge sets: the black edges and the red edges. If a black edge can be thought of as a full adjacency between its endpoints, and a non-edge, as a full non-adjacency, a red edge is a mixed state between the former two. Two vertices are called black neighbors (resp. red neighbors) if they are linked by a black edge (resp. a red edge). In a trigraph, a contraction of two (non-necessarily adjacent) vertices, say, u and v, merges the two vertices into a single vertex, say, w and link it with a black edge to vertices that are black neighbors of both u and v, and with a red edge to all the other neighbors of u or v.



A contraction sequence of an n-vertex (tri)graph G is a list of trigraphs G=Gn, Gn-1, ..., G2, G1 such that Gi is obtained from Gi+1 by performing one contraction. In particular G1 is the unique simple 1-vertex graph. A d-sequence is a contraction sequence such that the maximum red degree (that is, considering only the red edges) of every trigraph of the sequence is at most d. Finally the twin-width of a graph is the minimum integer d such that it admits a d-sequence. The following picture represents a contraction sequence witnessing that the initial 7-vertex (tri)graph has twin-width at most 2.




Classes with bounded twin-width: bounded cliquewidth classes, proper-minor closed classes, unit interval graphs, proper hereditary permutation classes, every graph whose edges are subdivided at least logarithmically many times, iterated O(1)-lifts, biclique-free segment graphs

Classes with unbounded twin-width: subcubic graphs, interval graphs, segment graphs, subdivisions of n-cliques where each edge is subdivided between one and o(log n) times, visibility graphs of simple polygons or even of 1.5D terrains

What is twin-width good for?

Contraction sequences are algorithmically useful: linear FPT algorithm for checking a first-order sentence on a graph (parameterized by the twin-width bound and the size of the first-order sentence), improved approximation algorithms for Minimum Dominating Set, Maximum Independent Set and Coloring

Structural properties of bounded twin-width classes: 𝛘-boundedness, even quasipolynomial 𝛘-boundedness, smallness (i.e., only exponentially many graphs on a given slice; extends, while using it, the Marcus-Tardos theorem)

Twin-width and finite model theory: Bounded twin-width is preserved by operating first-order transductions (useful fact to show that classes have or have not bounded twin-width), in some classes (see delineation in the Open Questions), like ordered graphs and tournaments, bounded/unbounded twin-width coincides with the tractability limit for first-order model checking.

The lens of contraction sequences: Adding additional (or different) constraints to the red graphs of the sequence, one retrieves the classical cliquewidth and linear cliquewidth, as well as a handful of new parameters interpolating between cliquewidth and twin-width, and one may recast Courcelle's theorems in an angle of view that unifies MSO and FO model checking algorithms.