Clique Separator Decomposition of Hole- and Diamond-Free Graphs and Algorithmic Consequences

Abstract

Clique separator decomposition introduced by Tarjan and Whitesides is one of the most important graph decompositions. A graph is an {\em atom} if it has no clique separator. A {\em hole} is a chordless cycle with at least five vertices, and an {\em antihole} is the complement graph of a hole. A graph is {\em weakly chordal} if it is hole- and antihole-free. $K_4-e$ is also called {\em diamond}. {\em Paraglider} has five vertices four of which induce a diamond, and the fifth vertex sees exactly the two vertices of degree two in the diamond. In this paper we show that atoms of hole- and diamond-free graphs (of hole- and paraglider-free graphs, respectively) are either weakly chordal or of a very specific structure. Hole- and paraglider-free graphs are perfect graphs. The structure of their atoms leads to efficient algorithms for various problems.

14 Pages, 1 figure