Even-hole-free graphs

In this thesis we consider the class of simple graphs defined by excluding even holes (i.e. chordless cycles of even length). These graphs are known as even-hole-free graphs. We first prove that every even-hole-free graph has a node whose neighborhood is triangulated. This implies that in an even-hole-free graph, with n nodes and m edges, there are at most n+2m maximal cliques. It also yields a fastest known algorithm for computing a maximum clique in an even-hole-free graph.

Afterwards we prove the main result of this thesis. The result is a decomposition theorem for even-hole-free graphs, that uses star cutsets and 2-joins. This is a significant strengthening of the only other previously known decomposition of even-hole-free graphs, by Conforti, Cornu´ejols, Kapoor and Vuˇskovi´c, that uses 2-joins and star, double star and triple star cutsets. It is also analogous to the decomposition of Berge (i.e. perfect) graphs with skew cutsets, 2-joins and their complements, by Chudnovsky, Robertson, Seymour and Thomas. In a graph that does not contain a 4-hole, a skew cutset reduces to a star cutset, and a 2-join in the complement implies a star cutset, so in a way it was expected that even-hole-free graphs can be decomposed with just the star cutsets and 2-joins.

A consequence of this decomposition theorem is an O(n19) recognition algorithm for even-hole-free graphs. The recognition of even-hole-free graphs was first shown to be polynomial by Conforti, Cornu´ejols, Kapoor and Vuˇskovi´c. They obtained an algorithm of complexity of about O(n40) by first preprocessing the input graph using a certain “cleaning” procedure, and then constructing a decomposition based recognition algorithm. The cleaning procedure was also the key to constructing a polynomial time recognition algorithm for Berge graphs. At that time it was observed by Chudnovsky and Seymour that once the cleaning is performed, one does not need a decomposition based algorithm, one can instead just look for the “bad structure” directly. Using this idea, as opposed to using the decomposition based approach, one gets significantly faster recognition algorithms for Berge graphs and balanced 0,±1 matrices. However, this approach yields an O(n31) recognition algorithm for even-hole-free graphs. So this is the first example of a decomposition based algorithm being significantly faster than the Chudnovsky/Seymour style algorithm.