Decomposition Theorem and Recognition Algorithm for Even-Hole-Free Graphs

Abstract: A hole in a graph is a chordless cycle of length greater than 3. In joint work with M. Conforti, G. Cornuéjols and A. Kapoor, we obtain a decomposition theorem for even-hole-free graphs (graphs that do not contain an even hole as an induced subgraph), based on which we construct a polynomial time recognition algorithm for this class of graphs. An analogous problem of recognizing odd-hole-free graphs remains open. Odd-hole-free graphs contain perfect graphs and if the Strong Perfect Graph Conjecture is true, their recognition would imply the recognition of perfect graphs. Part of our motivation for the study of even-hole-free graphs was to develop techniques which may then be used for the study of odd-hole-free graphs.