A lower bound on the tree-width of graphs with irrelevant vertices
A lower bound on the tree-width of graphs with irrelevant vertices
复制标题
DOI：
10.1016/j.jctb.2018.12.008
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Isolde Adler;P. K. Krause
中科院分区：
文献类型：
--
作者：
Isolde Adler;P. K. Krause
Robertson和Seymour证明了存在一个函数f使得如果一个图G的树宽至少为f（k），则G包含一个解无关的顶点（Robertson and Seymour（2012）[13]）。我们给出了f的单指数下界。这个界限甚至对平面图也成立。
For their famous algorithm for the disjoint paths problem, Robertson and Seymour proved that there is a function f such that if the tree-width of a graph G with k pairs of terminals is at least f (k), then G contains a solution-irrelevant vertex (Robertson and Seymour (2012)[13]). We give a single-exponential lower bound on f. This bound even holds for planar graphs.