×

A description of claw-free perfect graphs. (English) Zbl 0933.05062

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 V. Chvátal and 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.

MSC:

05C17 Perfect graphs
05C75 Structural characterization of families of graphs
05C85 Graph algorithms (graph-theoretic aspects)

Citations:

Zbl 0669.05054
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Berge, C., Graphs (1985), North-Holland: North-Holland Amsterdam/New York
[2] Chvátal, V.; Sbihi, N., Bull-free Berge graphs are perfect, Graphs Combin., 3, 127-139 (1987) · Zbl 0633.05056
[3] Chvátal, V.; Sbihi, N., Recognizing claw-free Berge graphs, J. Combin. Theory Ser. B, 44, 154-176 (1988) · Zbl 0669.05054
[4] Cornuéjols, G.; Cunningham, W., Compositions for perfect graphs, Discrete Math., 55, 245-254 (1985) · Zbl 0562.05043
[5] Gavril, F., Algorithms on clique separable graphs, Discrete Math., 19, 159-165 (1977) · Zbl 0378.05042
[6] Giles, R.; Trotter, L. E.; Tucker, A., The strong perfect graph theorem for a class of partitionable graphs, Topics on Perfect Graphs (1984), North-Holland: North-Holland Amsterdam, p. 161-167
[7] Hamelink, R. C., A partial characterization of clique graphs, J. Combin. Theory, 5, 192-197 (1968) · Zbl 0167.22203
[8] Harary, F.; Holzmann, C., Line graphs of bipartite graphs, Rev. Soc. Mat. Chile, 1, 19-22 (1974)
[9] Hsu, W. L.; Nemhauser, G. L., Algorithms for maximum weighted cliques, minimum weighted clique covers, and minimum colourings of claw-free perfect graphs, (Berge, C.; Chvátal, V., Topics on Perfect Graphs (1984), North-Holland: North-Holland Amsterdam) · Zbl 0561.05034
[10] Lovász, L., A characterization of perfect graphs, J. Combin. Theory Ser. B, 13, 95-98 (1972) · Zbl 0241.05107
[11] Parthasarathy, K. R.; Ravindra, G., The strong perfect graph conjecture is true for \(K_{1,3}\), J. Combin. Theory Ser. B, 21, 212-223 (1976) · Zbl 0297.05109
[12] Tarjan, R. E., Decomposition by clique separators, Discrete Math., 55, 221-232 (1985) · Zbl 0572.05039
[13] Whitesides, S. H., An algorithm for finding clique cut-sets, Inform. Process. Lett., 12, 31-32 (1981) · Zbl 0454.68078
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.