Twin-width II: small classes

• Published in: Combinatorial theory 2022-06, Vol.2 (2)
• Main Authors: Bonnet, Édouard, Geniet, Colin, Kim, Eun Jung, Thomassé, Stéphan, Watrigant, Rémi
• Format: Article
• Language: English
• Subjects: Computer Science; Mathematics
• ISSN: 2766-1334; 2766-1334
• DOI: 10.5070/C62257876

The recently introduced twin-width of a graph G is the minimum integer d such that G has a d-contraction sequence, that is, a sequence of |V (G)| − 1 iterated vertex identifications for which the overall maximum number of red edges incident to a single vertex is at most d, where a red edge appears between two sets of identified vertices if they are not homogeneous in G (not fully adjacent nor fully non-adjacent). We show that if a graph admits a d-contraction sequence, then it also has a linear-arity tree of f (d)-contractions, for some function f. Informally if we accept to worsen the twin-width bound, we can choose the next contraction from a set of Θ(|V (G)|) pairwise disjoint pairs of vertices. This has two main consequences. First it permits to show that every bounded twin-width class is small, i.e., has at most n!c n graphs labeled by [n], for some constant c. This unifies and extends the same result for bounded treewidth graphs [Beineke and Pippert, JCT '69], proper subclasses of permutations graphs [Marcus and Tardos, JCTA '04], and proper minor-free classes [Norine et al., JCTB '06]. It implies in turn that bounded-degree graphs, interval graphs, and unit disk graphs have unbounded twin-width. The second consequence is an O(log n)-adjacency labeling scheme for bounded twin-width graphs, confirming several cases of the implicit graph conjecture. We then explore the small conjecture that, conversely, every small hereditary class has bounded twin-width. The conjecture passes many tests. Inspired by sorting networks of logarithmic depth, we show that log Θ(log log d) n-subdivisions of K n (a small class when d is constant) have twin-width at most d. We obtain a rather sharp converse with a surprisingly direct proof: the log d+1 n-subdivision of K n has twin-width at least d. Secondly graphs with bounded stack or queue number (also small classes) have bounded twin-width. These sparse classes are surprisingly rich since they contain certain (small) classes of expanders. Thirdly we show that cubic expanders obtained by iterated random 2-lifts from K 4 [Bilu and Linial, Combinatorica '06] also have bounded twin-width. These graphs are related * All the authors were supported by the ANR projects (French National Research Agency) TWIN-WIDTH (ANR-21-CE48-0014-01) and Digraphs (ANR-19-CE48-0013-01). † supported by the ANR project ASSK (ANR-18-CE40-0025-01).