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)}$ for any fixed integer $d \geq 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.
Authors
- Sergey Norin (ORCID: https://orcid.org/0000-0003-4833-7983)
- Raphael Steiner (ORCID: https://orcid.org/0000-0002-4234-6136)
- Jérémie Turcotte (ORCID: https://orcid.org/0000-0002-4555-8425)
- Kevin Hendrey
Institutions
- ETH Zurich (CH)
- McGill University (CA)
- Monash University (AU)
Publication Details
- Journal
- Combinatorics Probability Computing
- Published
- 2024-12-11
- DOI
- https://doi.org/10.1017/s0963548324000439
- Citations
- 2
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 2.64
Funders
- Agence Nationale de la Recherche