Tight bound on treedepth in terms of pathwidth and longest path
Tight bound on treedepth in terms of pathwidth and longest path
复制标题
就路径宽度和最长路径而言，树深度的紧密界限
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Bartosz Walczak
中科院分区：
文献类型：
--
作者：
Meike Hatzel;G. Joret;Piotr Micek;Marcin Pilipczuk;T. Ueckerdt;Bartosz Walczak
我们证明了每个路径宽度严格小于$a$且不包含$2^b$顶点作为子图的路径的图的树深不超过$10ab$。边界是最好的，直到一个常数因子。
We show that every graph with pathwidth strictly less than $a$ that contains no path on $2^b$ vertices as a subgraph has treedepth at most $10ab$. The bound is best possible up to a constant factor.