Twin-width can be exponential in treewidth

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

Author name not available (Why is that?)

Publication date: 2 May 2023

Published in: (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

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

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)