Haven (graph Theory) - Connections To Treewidth, Separators, and Minors

Connections To Treewidth, Separators, and Minors

Havens may be used to characterize the treewidth of graphs: a graph has a haven of order k if and only if it has treewidth at least k − 1. A tree decomposition may be used to describe a winning strategy for the pursuers in the same pursuit-evasion game, so it is also true that a graph has a haven of order k if and only if the evader wins with best play against fewer than k pursuers. In games won by the evader, there is always an optimal strategy in the form described by a haven, and in games won by the pursuer, there is always an optimal strategy in the form described by a tree decomposition. For instance, because the 3 × 3 grid has a haven of order 4, but does not have a haven of order 5, it must have treewidth exactly 3. The same min-max theorem can be generalized to infinite graphs of finite treewidth, with a definition of treewidth in which the underlying tree is required to be rayless (that is, having no ends).

Havens are also closely related to the existence of separators, small sets X of vertices in an n-vertex graph such that every X-flap has at most 2n/3 vertices. If a graph G does not have a k-vertex separator, then every set X of at most k vertices has a (unique) X-flap with more than 2n/3 vertices. In this case, G has a haven of order k + 1, in which β(X) is defined to be this unique large X-flap. That is, every graph has either a small separator or a haven of high order.

If a graph G has a haven of order k, with k ≥ h3/2n1/2 for some integer h, then G must also have a complete graph K_h as a minor. In other words, the Hadwiger number of an n-vertex graph with a haven of order k is at least k2/3n−1/3. As a consequence, the K_h-minor-free graphs have treewidth less than h3/2n1/2 and separators of size less than h3/2n1/2. More generally an O(√n) bound on treewidth and separator size holds for any nontrivial family of graphs that can be characterized by forbidden minors, because for any such family there is a constant h such that the family does not include K_h.