Twin-width can be exponential in treewidth

Abstract

For any small positive real $\epsilon$ and integer $t>\frac{1}{\epsilon }$, we build a graph with a vertex deletion set of size $t$ to a tree, and twin-width greater than $2^{(1-\epsilon )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-\epsilon$. Except for the one in oriented twin-width, these lower bounds are essentially tight.

11 pages, 2 figures