SIAM Journal on Discrete Mathematics, 10:1 (1997).

The structure and number of obstructions to treewidth

Siddharthan Ramachandramurthi

Abstract

For each pair of non-adjacent vertices in a graph, consider the greater of the degrees of the two vertices. The minimum of these maxima is a lower bound on the treewidth of a graph, unless it is a complete graph. This bound has three consequences. First, the obstructions of order w+3 for treewidth w have a simple structural characterization. Second, these graphs are exactly the pathwidth obstructions of order w+3. Finally, although there is only one obstruction of order w+2 for width w, the number of obstructions of order w+3 is bounded below by an exponential function of sqrt(w).


siddhart@cs.utk.edu