BOUNDS FOR THE TWIN-WIDTH OF GRAPHS

Abstract

Bonnet et al. [J. ACM, 69 (2022), 3] introduced the twin-width of a graph. We show that the twin-width of an n-vertex graph is less than (Formmula presented), and the twin-width of an m-edge graph for a positive m is less than (Formmula presented). Conference graphs of order n (when such graphs exist) have twin-width at least (n − 1)/2, and we show that Paley graphs achieve this lower bound. We also show that the twin-width of the Erdős–Rényi random graph G(n, p) with 1/n ≤ p ≤ 1/2 is larger than (Formmula presented) ln n asymptotically almost surely for any positive ε. Last, we calculate the twin-width of random graphs G(n, p) with p ≤ c/n for a constant c < 1, determining the thresholds at which the twin-width jumps from 0 to 1 and from 1 to 2. © 2022 Society for Industrial and Applied Mathematics.