twin-width

abbr: tww

providers: PACE

Definition: A contraction sequence for a graph $G$ is a sequence of $n-1$ contractions – identification of two not necessarily adjacent vertices. Note that at any point each vertex of a partially contracted graph represents a subset of vertices in the original graph. Vertices of a partially contracted graph are joined with an edge if there is a complete bipartite graph between the represented subsets of vertices in the original graph. Similarly, there is a non-edge if the two sets have no edges between them. Last, there is a red-edge is there are some edges and some non-edges. Red degree of a partially contracted graph is the maximum number of red edges adjacent to a single vertex. Twin-width is the minimum over contraction sequences of maximum over the sequence’s red degree.

Relations

Results

• 2024 Twin-width of graphs on surfaces by Kráľ, Pekárková, Štorgel
  • page 18 : genus upper bounds twin-width by a linear function – The twin-width of every graph $G$ of Euler genus $g \ge 1$ is at most … $18 \sqrt{47g}+O(1)$.
• 2024 Merge-width and First-Order Model Checking by Dreier, Toruńczyk
  • page 6 : twin-width upper bounds merge-width by a computable function – Theorem 1.4. Graph classes of bounded twin-width have bounded merge-width.
• 2023 Flip-width: Cops and Robber on dense graphs by Toruńczyk
  • twin-width upper bounds radius-r flip-width by an exponential function – Theorem 7.1. Fix $r \in \mathbb N$. For every graph $G$ of twin-width $d$ we have: $\mathrm{fw}_r(G) \le 2^d \cdot d^{O(r)}$.
• 2022 Expanding the Graph Parameter Hierarchy by Tran
  • page 36 : clique-width upper bounds twin-width by a tower function – Proposition 6.2. Clique-width strictly upper bounds Twin-width.
  • page 36 : graph classes with bounded twin-width are not bounded clique-width – Proposition 6.2. Clique-width strictly upper bounds Twin-width.
  • page 37 : genus upper bounds twin-width by a linear function – Proposition 6.3. Genus strictly upper bounds Twin-width.
  • page 37 : graph classes with bounded twin-width are not bounded genus – Proposition 6.3. Genus strictly upper bounds Twin-width.
  • page 37 : distance to planar upper bounds twin-width by an exponential function – Theorem 6.4. Distance to Planar strictly upper bounds Twin-width.
  • page 37 : graph classes with bounded twin-width are not bounded distance to planar – Theorem 6.4. Distance to Planar strictly upper bounds Twin-width.
  • page 38 : graph classes with bounded twin-width are not bounded distance to interval – Observation 6.5. Twin-width is incomparable to Distance to Interval.
  • page 38 : graph classes with bounded distance to interval are not bounded twin-width – Observation 6.5. Twin-width is incomparable to Distance to Interval.
  • page 38 : graph classes with bounded twin-width are not bounded distance to bipartite – Proposition 6.6. Twin-width is incomparable to Distance to Bipartite.
  • page 38 : graph classes with bounded distance to bipartite are not bounded twin-width – Proposition 6.6. Twin-width is incomparable to Distance to Bipartite.
  • page 40 : graph classes with bounded twin-width are not bounded clique cover number – Proposition 6.7. Twin-width is incomparable to Clique Cover Number.
  • page 40 : graph classes with bounded clique cover number are not bounded twin-width – Proposition 6.7. Twin-width is incomparable to Clique Cover Number.
  • page 40 : graph classes with bounded twin-width are not bounded maximum degree – Proposition 6.8. Twin-width is incomparable to Maximum Degree.
  • page 40 : graph classes with bounded maximum degree are not bounded twin-width – Proposition 6.8. Twin-width is incomparable to Maximum Degree.
  • page 40 : graph classes with bounded twin-width are not bounded bisection bandwidth – Observation 6.9. Twin-width is incomparable to Bisection Width.
  • page 40 : graph classes with bounded bisection bandwidth are not bounded twin-width – Observation 6.9. Twin-width is incomparable to Bisection Width.
• 2021 Twin-width I: Tractable FO Model Checking by Bonnet, Kim, Thomassé, Watrigant
  • page 2 : twin-width – … we consider a sequence of graphs $G_n,G_{n-1},\dots,G_2,G_1$, where $G_n$ is the original graph $G$, $G_1$ is the one-vertex graph, $G_i$ has $i$ vertices, and $G_{i-1}$ is obtained from $G_i$ by performing a single contraction of two (non-necessarily adjacent) vertices. For every vertex $u \in V(G_i)$, let us denote by $u(G)$ the vertices of $G$ which have been contracted to $u$ along the sequence $G_n,\dots,G_i$. A pair of disjoint sets of vertices is \emph{homogeneous} if, between these sets, there are either all possible edges or no edge at all. The red edges … consist of all pairs $uv$ of vertices of $G_i$ such that $u(G)$ and $v(G)$ are not homogeneous in $G$. If the red degree of every $G_i$ is at most $d$, then $G_n,G_{n-1},\dots,G_2,G_1$ is called a \emph{sequence of $d$-contractions}, or \emph{$d$-sequence}. The twin-width of $G$ is the minimum $d$ for which there exists a sequence of $d$-contractions.
  • page 14 : boolean width upper bounds twin-width by an exponential function – Theorem 3: Every graph with boolean-width $k$ has twin-width at most $2^{k+1}-1$.
  • page 15 : grid upper bounds twin-width by a constant – Theorem 4.3. For every positive integers $d$ and $n$, the $d$-dimensional $n$-grid has twin-width at most $3d$.
• assumed
  • sparse twin-width upper bounds twin-width by a linear function – by definition
  • twin-width is equivalent to twin-width – assumed
• unknown source
  • clique-width upper bounds twin-width by a tower function
  • twin-width upper bounds monadically dependent by a constant
  • sparse twin-width upper bounds twin-width by a linear function