A description of claw-free perfect graphs (Q1306428): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Bruce A. Reed / rank | |||
Property / author | |||
Property / author: Bruce A. Reed / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2076296189 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3680833 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bull-free Berge graphs are perfect / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recognizing claw-free perfect graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Compositions for perfect graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithms on clique separable graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3218158 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A partial characterization of clique graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5184940 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A characterization of perfect graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Decomposition by clique separators / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An algorithm for finding clique cut-sets / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 09:30, 29 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A description of claw-free perfect graphs |
scientific article |
Statements
A description of claw-free perfect graphs (English)
0 references
4 April 2000
0 references
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.
0 references
Berge graphs
0 references
claw-free graph
0 references
polynomial algorithm
0 references
perfect graphs
0 references
structural characterization
0 references
elementary graph
0 references
connected graph
0 references
line graph
0 references
wonders
0 references
augmentation
0 references
matching
0 references
bipartite multigraph
0 references