pith. sign in

arxiv: 1901.04325 · v1 · pith:GOSB3WMXnew · submitted 2019-01-14 · 💻 cs.DM · math.CO

A lower bound on the tree-width of graphs with irrelevant vertices

classification 💻 cs.DM math.CO
keywords boundgraphgraphslowertree-widthalgorithmcontainsdisjoint
0
0 comments X
read the original abstract

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 (Graph Minors. XXII., JCTB 2012). We give a single-exponential lower bound on $f$. This bound even holds for planar graphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.