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.
- 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
- 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)
