A description of claw-free perfect graphs (Q1306428): Difference between revisions

Claw-free Berge graphs are known to be perfect. Chvátal and Sbihi proved that a claw-free graph is Berge if and only if every leaf in any clique-cutset decomposition tree of the graph is either ``peculiar'' or ``elementary,'' thus providing a polynomial algorithm for recognizing claw-free perfect graphs; see \textit{V. Chvátal} and \textit{N. Sbihi} [J. Comb. Theory, Ser. B 44, No. 2, 154-176 (1988; Zbl 0669.05054)]. Their definition of peculiar graphs completely describes their structure. But elementary graphs are defined as those whose edges admit a bicoloring in such a way that every chordless path on three vertices (a \(P_3\)) has its two edges colored differently. The main result of this paper is the following structural characterization of elementary graph: ``For a connected graph \(G\) the following properties are equivalent: (1) \(G\) is elementary. (2) \(G\) is claw-free Berge and contains none of the five ``wonders.'' (3) \(G\) is an augmentation of the line graph of a bipartite multigraph.'' The wonders are five small graphs called pyramid, lighthouse, mausoleum, garden and colossus. Augmenting a flat edge \(xy\) (an edge not lying in any triangle) is a process of attaching a cobipartite graph \(B\) (disjoint from \(G\)) to \(G-\{x,y\}\) in a specified way and a general augmentation is repeated augmentation of a set of flat edges forming a matching in \(G\). As a prelude to the main theorem, the authors prove the following characterizations which are of independent interest: (1) A graph is the line graph of a bipartite multigraph if and only if it contains no claw, no 4-wheel and no odd hold. (2) A connected graph is either the line graph of a bipartite multigraph or the complement of a bipartite graph if and only if it contains no claw, no odd hole, no odd antihole, no \(D\) and no pyramid. Here \(D\) is a graph on six vertices \(x\), \(0\), \(1\), \(2\), \(3\), \(4\) and edes so that \(x0234\) is a chordless path and \(1\) is adjacent to all the other vertices except \(x\). Besides a polynomial algorithm implicit in the proof of the main theorem, the authors provide a canonical decomposition algorithm for elementary graphs, and also give an alternative proof of the well-known result that every claw-free Berge graph is perfect.