Bounds for the Twin-Width of Graphs

DOI10.1137/21M1452834zbMATH Open1498.05235arXiv2110.03957OpenAlexW3206499916WikidataQ131573536 ScholiaQ131573536MaRDI QIDQ5043639

Author name not available (Why is that?)

Publication date: 6 October 2022

Published in: (Search for Journal in Brave)

Abstract: Bonnet, Kim, Thomass'{e}, 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+sqrtnlnn+sqrtn+2lnn)/2$, and the twin-width of an $m$-edge graph for a positive $m$ is less than $sqrt3m+m^{1/4}sqrtlnm/(4cdot{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 ErdH{o}s-R'{e}nyi random graph $G(n,p)$ with $1/nleqp=p(n)leq1/2$ is larger than $2p(1-p)n-(2sqrt2+varepsilon)sqrtp(1-p)nlnn$ asymptotically almost surely for any positive $varepsilon$. Lastly, we calculate the twin-width of random graphs $G(n,p)$ with $pleqc/n$ for a constant $c<1$, determining the thresholds at which the twin-width jumps from $0$ to $1$ and from $1$ to $2$.

Full work available at URL: https://arxiv.org/abs/2110.03957

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Bounds for the Twin-Width of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5043639)