twin-width

abbr: tww

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)$.
• 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 : bounded twin-width does not imply 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 : bounded twin-width does not imply 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 : bounded twin-width does not imply bounded distance to planar – Theorem 6.4. Distance to Planar strictly upper bounds Twin-width.
  • page 38 : bounded twin-width does not imply bounded distance to interval – Observation 6.5. Twin-width is incomparable to Distance to Interval.
  • page 38 : bounded distance to interval does not imply bounded twin-width – Observation 6.5. Twin-width is incomparable to Distance to Interval.
  • page 38 : bounded twin-width does not imply bounded distance to bipartite – Proposition 6.6. Twin-width is incomparable to Distance to Bipartite.
  • page 38 : bounded distance to bipartite does not imply bounded twin-width – Proposition 6.6. Twin-width is incomparable to Distance to Bipartite.
  • page 40 : bounded twin-width does not imply bounded clique cover number – Proposition 6.7. Twin-width is incomparable to Clique Cover Number.
  • page 40 : bounded clique cover number does not imply bounded twin-width – Proposition 6.7. Twin-width is incomparable to Clique Cover Number.
  • page 40 : bounded twin-width does not imply bounded maximum degree – Proposition 6.8. Twin-width is incomparable to Maximum Degree.
  • page 40 : bounded maximum degree does not imply bounded twin-width – Proposition 6.8. Twin-width is incomparable to Maximum Degree.
  • page 40 : bounded twin-width does not imply bounded bisection bandwidth – Observation 6.9. Twin-width is incomparable to Bisection Width.
  • page 40 : bounded bisection bandwidth does not imply 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$.
• unknown source
  • clique-width upper bounds twin-width by a tower function
• assumed
  • twin-width is equivalent to twin-width – assumed