The central bag method: An approach to analyzing the structure of hereditary graph classes

Abstract

In this thesis we develop the central bag method. The central bag method uses the structure of cutsets in a graph G to construct an induced subgraph B of G with two key features: 1. Every component of G - B has small weight and has constant-size neighborhood in B; and 2. the properties of B are "nicer'" than the properties of G. The central bag was inspired by properties of tree decompositions and is analogous to a single bag of a well-chosen tree decomposition of G.

The main application of the central bag method is to prove that hereditary graph classes have bounded treewidth. In this thesis, we show how the central bag method can be used to prove that (theta, pyramid, prism, line wheel, Kt)-free graphs have logarithmic treewidth (in the number of vertices), that (even hole, pyramid, diamond, Kt)-free graphs have constant treewidth, and that (propeller, Wtxt, Kt)-free graphs have constant treewidth. The central bag method has also been used to prove that the Maximum Weight Independent Set problem (MWIS) is polynomial-time solvable in certain hereditary graph classes. In this thesis, we show how the central bag method can be used to prove that MWIS is polynomial-time solvable in a subclass of perfect graphs and in (Sttt, Kt, Ktt)-free graphs.