New classes of perfect graphs (Q1087552)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New classes of perfect graphs |
scientific article |
Statements
New classes of perfect graphs (English)
0 references
1986
0 references
\textit{R. B. Hayward} [J. Comb. Theory, Ser. B 39, 200-208 (1985; Zbl 0551.05055)] called a graph weakly triangulated if it did not contain as an induced subgraph a cycle of length \(\geq 5\) without a chord, or its complement. He showed such graphs are perfect. The author and \textit{P. Duchet} [Ann. Discrete Math. 21, 57-61 (1984; Zbl 0558.05037)] called a graph G strongly perfect if some subset of vertices contained exactly one vertex from each maximal clique of G. They characterized those strongly perfect graphs that are also perfect. \textit{H. Meyniel} called a graph G a quasi-parity graph if for every \(A\subseteq V(G)\), \(<A>\) not a clique, A has two members x and y are not connected by a chordless odd path in the induced subgraph \(<A>\). He showed that every quasi-parity graph is perfect. The present author surveys the main properties of these new classes in order to compare them with the more commonly known perfect graphs.
0 references
strongly perfect graphs
0 references
quasi-parity graph
0 references