The (theta, wheel)-free graphs Part II: Structure theorem

Abstract

A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three paths between the same pair of distinct vertices so that the union of any two of the paths induces a hole. A wheel is a graph formed by a hole and a node that has at least 3 neighbors in the hole. In this paper we obtain a decomposition theorem for the class of graphs that do not contain an induced subgraph isomorphic to a theta or a wheel, i.e. the class of (theta, wheel)-free graphs. The decomposition theorem uses clique cutsets and 2-joins. Clique cutsets are vertex cutsets that work really well in decomposition based algorithms, but are unfortunately not general enough to decompose more complex hereditary graph classes. A 2-join is an edge cutset that appeared in decomposition theorems of several complex classes, such as perfect graphs, even-hole-free graphs and others. In these decomposition theorems 2-joins are used together with vertex cutsets that are more general than clique cutsets, such as star cutsets and their generalizations (which are much harder to use in algorithms). This is a first example of a decomposition theorem that uses just the combination of clique cutsets and 2-joins. This has several consequences. First, we can easily transform our decomposition theorem into a complete structure theorem for (theta, wheel)-free graphs, i.e. we show how every (theta, wheel)-free graph can be built starting from basic graphs that can be explicitly constructed, and gluing them together by prescribed composition operations; and all graphs built this way are (theta, wheel)-free. Such structure theorems are very rare for hereditary graph classes, only a few examples are known. Secondly, we obtain an O(n4m)-time decomposition based recognition algorithm for (theta, wheel)-free graphs. Finally, in Parts III and IV of this series, we give further applications of our decomposition theorem.