Structural Characterisations of Hereditary Graph Classes and Algorithmic Consequences

A hole is a chordless cycle of length at least four, and is even or odd depending onthe parity of its length. Many interesting classes of graphs are defined by excluding (possibly among other graphs) holes of certain lengths. Most famously perhaps is the class of Berge graphs, which are the graphs that contain no odd hole and no complement of an odd hole. A graph is perfect if the chromatic number of each of its induced subgraphs is equal to the size of a maximum clique in that subgraph. It was conjectured in the 1960’s by Claude Berge that Berge graphs and perfect graphs are equivalent, that is, a graph is perfect if and only if it is Berge. This conjecture was finally resolved by Chudnovsky, Robertson, Seymour and Thomas in 2002, and it is now called the strong perfect graph theorem.

Graphs that do not contain even holes are structurally similar to Berge graphs, and for this reason Conforti, Cornuéjols, Kapoor and Vušković initiated the study of even-hole-free graphs. One of their main results was a decomposition theorem and a recognition algorithm for even-hole-free graphs, and many techniques developed in the pursuit of a decomposition theorem for even-hole-free graphs proved useful in the study of perfect graphs. Indeed, the proof of the strong perfect graph theorem relied on decomposition, and many interesting graph classes have since then been understood from the viewpoint of decomposition.

In this thesis we study several classes of graphs that relate to even-hole-free graphs. First, we focus on β-perfect graphs, which form a subclass of even-hole-free graphs. While it is unknown whether even-hole-free graphs can be coloured in polynomial time, β-perfect graphs can be coloured optimally in polynomial time using the greedy colouring algorithm. The class of β-perfect graphs was introduced in 1996 by Markossian, Gasparian and Reed, and since then several classes of β-perfect graphs have been identified but no forbidden induced subgraph characterisation is known. In this thesis we identify a new class of β-perfect graphs, and we present forbidden induced subgraph characterisations for the class of β-perfect hyperholes and for the class of claw-free β-perfect graphs. We use these characterisations to decide in polynomial time whether a given hyperhole, or more generally a claw-free graph, is β-perfect.

A graph is l-holed (for an integer l ≥ 4) if every one of its holes is of length l. Another focus of the thesis is the class of l-holed graphs. When l is odd, the l-holed graphs form a subclass of even-hole-free graphs. Together with Preissmann, Robin, Sintiari, Trotignon and Vušković we obtained a structure theorem for l-holed graphs where l ≥ 7. Working independently, Cook and Seymour obtained a structure theorem for the same class of graphs. In this thesis we establish that these two structure theorems are equivalent. Furthermore, we present two recognition algorithms for l-holed graphs for odd l ≥ 7. The firs uses the structure theorem of Preissmann, Robin,
Sintiari, Trotignon, Vušković and the present author, and relies on decomposition by a new variant of a 2-join called a special 2-join, and the second uses the structure theorem of Cook and Seymour, and relies only on a process of clique cutset decomposition. We also give algorithms that solve in polynomial time the maximum clique and maximum stable set problems for l-holed graphs for odd l ≥ 7.

Finally, we focus on circular-arc graphs. It is a long standing open problem to characterise in terms of forbidden induced subgraphs the class of circular-arc graphs, and even the class of chordal circular-arc graphs. Motivated by a result of Cameron, Chap-lick and Hoàng stating that even-hole-free graphs that are pan-free can be decomposed by clique cutsets into circular-arc graphs, we investigate the class of even-hole-free circular-arc graphs. We present a partial characterisation for the class of even-hole-free circular-arc graphs that are not chordal.