Twin-width can be exponential in treewidth

DOI10.1016/J.JCTB.2023.01.003zbMATH Open1514.05131arXiv2204.07670MaRDI QIDQ6038574FDOQ6038574

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)

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.

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

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

zbMATH Keywords

treewidthfeedback vertex setmixed minor

Mathematics Subject Classification ID

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

Cites Work

• Lifts, discrepancy and nearly optimal spectral gap
• Title not available (Why is that?)
• Bounds for the twin-width of graphs
• Twin-width and polynomial kernels
• Title not available (Why is that?)
• Twin-width. I: Tractable FO model checking
• Twin-width II: small classes
• Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
• Twin-width and transductions of proper \(k\)-mixed-thin graphs

Cited In (6)

• Neighbourhood complexity of graphs of bounded twin-width
• Twin-width of random graphs
• Bounds for the twin-width of graphs
• Twin-width of graphs with tree-structured decompositions
• Twin-width. I: Tractable FO model checking
• Bounds on the Twin-Width of Product Graphs

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)