Twin-width of sparse random graphs

Abstract

We show that the twin-width of every $n$-vertex $d$-regular graph is at most $n^{\frac{d-2}{2d-2}+o(1)}$ and that almost all $d$-regular graphs attain this bound. More generally, we obtain bounds on the twin-width of sparse Erdős-Renyi and regular random graphs, complementing the bounds in the denser regime due to Ahn, Chakraborti, Hendrey, Kim and Oum.

arXiv comment22 pages

References in corpus (3)

• The densest subgraph problem in sparse random graphs
• Bounds for the Twin-width of Graphs
• Twin-width of random graphs

Cited by in corpus (1)

• On the twin-width of near-regular graphs