Twin-width of sparse random graphs
METADATA ONLY
Loading...
Author / Producer
Date
2025-05
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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)}$ for any fixed integer d ≥ 2 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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
34 (3)
Pages / Article No.
401 - 420
Publisher
Cambridge University Press
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Twin-width; random graphs
Organisational unit
Notes
Funding
216071 - Graph coloring motivated by Hadwiger's conjecture (SNF)