On tree decompositions whose trees are minors
On tree decompositions whose trees are minors
复制标题
关于次树的树分解
DOI：
10.1002/jgt.23083
复制
发表时间：
2024
影响因子：
0.9
通讯作者：
Blanco P
中科院分区：
文献类型：
--
作者：
Blanco P
在2019年，Dvovenák提出了一个问题：是否每个连通图G $G$都有一个树分解（T，B）$（T，{\rm{ {\mathcal B} }）$，使得T $T$是G $G$的子图，并且（T，B）$（T，{\rm{ {\mathcal B}}）$的宽度由G $G$的树宽度的函数来界定。我们证明这是假的，即使当G $G$有树宽2和T $T$允许是G $G$的一个小的。
In 2019, Dvořák asked whether every connected graph G $G$ has a tree decomposition ( T , B ) $(T,{\rm{ {\mathcal B} }})$ so that T $T$ is a subgraph of G $G$ and the width of ( T , B ) $(T,{\rm{ {\mathcal B} }})$ is bounded by a function of the treewidth of G $G$. We prove that this is false, even when G $G$ has treewidth 2 and T $T$ is allowed to be a minor of G $G$.
登录
查看更多内容
大路径宽度的二连通图的次数
DOI：
--
发表时间：
2017
期刊：
arXiv.org
影响因子：
--
作者：
Thanh N. Dang;R. Thomas
通讯作者：
R. Thomas
改进了树深度的排除次要近似值的界限
DOI：
--
发表时间：
2019
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
Wojciech Czerwinski;Wojciech Nadara;Marcin Pilipczuk
通讯作者：
Marcin Pilipczuk
有界高度树和树深度
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
J. Nesetril;P. D. Mendez
通讯作者：
P. D. Mendez
就路径宽度和最长路径而言，树深度的紧密界限
DOI：
--
发表时间：
2023
期刊：
Comb.
影响因子：
--
作者：
Meike Hatzel;G. Joret;Piotr Micek;Marcin Pilipczuk;T. Ueckerdt;Bartosz Walczak
通讯作者：
Bartosz Walczak
网格小定理的多项式界
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
C. Chekuri;Julia Chuzhoy
通讯作者：
Julia Chuzhoy