Bounds for the Twin-width of Graphs

Abstract

Bonnet, Kim, Thomassé, and Watrigant (2020) introduced the twin-width of a graph. We show that the twin-width of an $n$-vertex graph is less than $(n+\sqrt{n\ln n}+\sqrt{n}+2\ln n)/2$, and the twin-width of an $m$-edge graph for a positive $m$ is less than $\sqrt{3m}+m^{1/4}\sqrt{\ln m}/(4\cdot 3^{1/4})+3m^{1/4}/2$. 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\le p=p(n)\le 1/2$ is larger than $2p(1-p)n-(2\sqrt{2}+\epsilon )\sqrt{p(1-p)n\ln n}$ asymptotically almost surely for any positive $\epsilon$. Lastly, we calculate the twin-width of random graphs $G(n,p)$ with $p\le 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$.

22 pages, 1 figure

References in corpus (1)

• Ordered graphs of bounded twin-width

Cited by in corpus (5)

• Twin-width of subdivisions of multigraphs
• Twin-width of random graphs
• Bounds on the Twin-Width of Product Graphs
• Twin-width of sparse random graphs
• On the twin-width of near-regular graphs