On tree decompositions whose trees are minors
Autor: | Blanco, Pablo, Cook, Linda, Hatzel, Meike, Hilaire, Claire, Illingworth, Freddie, McCarty, Rose |
---|---|
Rok vydání: | 2023 |
Předmět: | |
Druh dokumentu: | Working Paper |
Popis: | In 2019, Dvo\v{r}\'{a}k asked whether every connected graph $G$ has a tree decomposition $(T, \mathcal{B})$ so that $T$ is a subgraph of $G$ and the width of $(T, \mathcal{B})$ is bounded by a function of the treewidth of $G$. We prove that this is false, even when $G$ has treewidth $2$ and $T$ is allowed to be a minor of $G$. Comment: 10 pages, 2 figures |
Databáze: | arXiv |
Externí odkaz: |
načítá se...