A description of claw-free perfect graphs
type: Item
instance of: scholarly article
title: A description of claw-free perfect graphs
zbMATH Open document ID: 0933.05062
author: Frédéric Maffray
author: Bruce Reed
published in: Journal of Combinatorial Theory. Series B
publication date: 2000-04-04T00:00:00Z
review text: 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 v…
Mathematics Subject Classification ID: 05C17
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1347242
zbMATH Keywords: Berge graphs
zbMATH Keywords: claw-free graph
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: perfect graphs
zbMATH Keywords: structural characterization
zbMATH Keywords: elementary graph
zbMATH Keywords: connected graph
zbMATH Keywords: line graph
zbMATH Keywords: wonders
zbMATH Keywords: augmentation
zbMATH Keywords: matching
zbMATH Keywords: bipartite multigraph
MaRDI profile type: Publication
OpenAlex ID: W2076296189
cites work: Q3680833
cites work: Bull-free Berge graphs are perfect
cites work: Recognizing claw-free perfect graphs
cites work: Compositions for perfect graphs
cites work: Algorithms on clique separable graphs
cites work: Q3218158
cites work: A partial characterization of clique graphs
cites work: Q5184940
cites work: A characterization of perfect graphs
cites work: The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
cites work: Decomposition by clique separators
cites work: An algorithm for finding clique cut-sets
DOI: 10.1006/JCTB.1998.1872
description: scientific article; zbMATH DE number 1347242