Back to Search Start Over

Twin-width can be exponential in treewidth.

Authors :
Bonnet, Édouard
Déprés, Hugues
Source :
Journal of Combinatorial Theory - Series B. Jul2023, Vol. 161, p1-14. 14p.
Publication Year :
2023

Abstract

For any small positive real ε and integer t > 1 ε , we build a graph with a vertex deletion set of size t to a tree, and twin-width greater than 2 (1 − ε) 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 − ε. Except for the one in oriented twin-width, these lower bounds are essentially tight. [ABSTRACT FROM AUTHOR]

Subjects

Subjects :
*TREE size
*INTEGERS

Details

Language :
English
ISSN :
00958956
Volume :
161
Database :
Academic Search Index
Journal :
Journal of Combinatorial Theory - Series B
Publication Type :
Academic Journal
Accession number :
163308520
Full Text :
https://doi.org/10.1016/j.jctb.2023.01.003