New classes of perfect graphs

DOI10.1016/0166-218X(86)90038-7MaRDI QIDQ1087552zbMATH OpenFDO

Authors C. Berge

Publication date 1986

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(86)90038-7

zbMATH Keywords

quasi-parity graph strongly perfect graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Graph theory (05C99)

Review text

\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.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: New classes of perfect graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1087552)