Twin-width can be exponential in treewidth (Q6038574)

A trigraph is a graph with some edges colored black, and some colored red. A (vertex) contraction consists of merging two non-necessarily adjacent) vertices, say, \(u, v\) into a vertex \(w\), and keeping every edge \(wz\) black if and only if \(uz\) and \(vz\) were previously black edges. The other edges incident to \(w\) become red (if not already), and the rest of the trigraph remains the same. A contraction sequence of an \(n\)-vertex graph \(G\) is a sequence of trigraphs \(G = G_n, \dots, G_1 = K_1\) such that \(G_i\) is obtained from \(G_{i+1}\) by performing one contraction. A \(d\)-sequence is a contraction sequence in which every vertex of every trigraph has at most \(d\) red edges incident to it. The twin-width of \(G\), denoted by \(tww(G)\), is then the minimum integer \(d\) such that \(G\) admits a \(d\)-sequence. In this paper, the authors obtain the following result: For every real \(0< \varepsilon\leq 1/2\) and integer \(t > 1/\varepsilon\), there is a graph \(G_{t,\varepsilon}\) with a feedback vertex set of size \(t\) and such that \(tww(G_{t,\varepsilon}) > 2^{(1-\varepsilon)t}\). In particular, their result 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.