Bounds for the twin-width of graphs

DOI10.1137/21M1452834MaRDI QIDQ5043639zbMATH OpenOpenAlexWikidataFDO

Authors Jung-Ho Ahn, Kevin Hendrey, Donggyu Kim, Sang-Il Oum

Publication date 6 October 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

extremal graphsPaley graphrandom graphstwin-width

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Extremal problems in graph theory (05C35)

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$.

Recommendations

• Twin-width can be exponential in treewidth
• Twin-width II: small classes
• Graphs of bounded twin-width are quasi-polynomially -bounded
• Twin-width and generalized coloring numbers
• A note on treewidth in random graphs

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A bound on the pathwidth of sparse graphs with applications to exact algorithms
• Asymmetric graphs
• Handbook of Enumerative Combinatorics
• Rank-width of random graphs
• The rank-width of the square grid
• Twin-width II: small classes
• Twin-width and generalized coloring numbers
• Twin-width and polynomial kernels
• Twin-width. I: Tractable FO model checking

Cited in

(25)

• Bounds on the Twin-Width of Product Graphs
• Graphs of bounded twin-width are quasi-polynomially -bounded
• Twin-width can be exponential in treewidth
• Twin-width of graphs on surfaces
• Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
• Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
• A characterization of graphs of radius-r flip-width at most 2
• Planar graph with twin-width seven
• Improved bounds for twin-width parameter variants with algorithmic applications to counting graph colorings
• Twin-width of sparse random graphs
• Randomized communication and implicit graph representations
• Neighbourhood complexity of graphs of bounded twin-width
• Twin-width of random graphs
• Twin-width meets feedback edges and vertex integrity
• Twin-width IV: ordered graphs and matrices
• Computing and certifying twin-width using logic
• Twin-width of graphs with tree-structured decompositions
• On the twin-width of near-regular graphs
• Twin-width and generalized coloring numbers
• Twin-width of graphs with tree-structured decompositions
• Computing twin-width parameterized by the feedback edge number and vertex integrity
• Twin-width of planar graphs is at most 8, and some related bounds
• Graph product structure for \(h\)-framed graphs
• PACE solver description: RedAlert -- heuristic track
• Twin-width of subdivisions of multigraphs

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)