Twin-width can be exponential in treewidth

DOI10.1016/J.JCTB.2023.01.003MaRDI QIDQ6038574zbMATH OpenFDO

Authors Édouard Bonnet, Hugues Déprés

Publication date 2 May 2023

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

feedback vertex setmixed minortreewidth

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph minors (05C83)

Abstract: For any small positive real $varepsilon$ and integer $t>frac1varepsilon$, we build a graph with a vertex deletion set of size $t$ to a tree, and twin-width greater than $2^{(1-varepsilon)t}$. In particular, this shows that the twin-width is sometimes exponential in the treewidth, in the so-called oriented twin-width and grid number, and that adding an apex may multiply the twin-width by at least $2-varepsilon$. Except for the one in oriented twin-width, these lower bounds are essentially tight.

Recommendations

• Bounds for the twin-width of graphs
• Twin-width II: small classes
• Twin-width and generalized coloring numbers
• Twin-width. I: Tractable FO model checking
• On the Relationship Between Clique-Width and Treewidth

Cites work

• Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
• Bounds for the twin-width of graphs
• scientific article; zbMATH DE number 7489399 (Why is no real title available?)
• scientific article; zbMATH DE number 7638379 (Why is no real title available?)
• Lifts, discrepancy and nearly optimal spectral gap
• Twin-width and polynomial kernels
• Twin-width and transductions of proper k-mixed-thin graphs
• Twin-width II: small classes
• Twin-width. I: Tractable FO model checking

Cited in

(11)

• Bounds for the twin-width of graphs
• Twin-width. I: Tractable FO model checking
• Neighbourhood complexity of graphs of bounded twin-width
• Bounds on the Twin-Width of Product Graphs
• Twin-width of random graphs
• Twin-width of graphs with tree-structured decompositions
• Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
• Randomized communication and implicit graph representations
• Twin-width of graphs with tree-structured decompositions
• A characterization of graphs of radius-r flip-width at most 2
• Improved bounds for twin-width parameter variants with algorithmic applications to counting graph colorings

This page was built for publication: Twin-width can be exponential in treewidth

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