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

Isolde Adler, Philipp Klaus Krause

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 te…