A new property of critical imperfect graphs and some consequences
type: Item
instance of: scholarly article
title: A new property of critical imperfect graphs and some consequences
zbMATH Open document ID: 0647.05053
DOI: 10.1016/S0195-6698(87)80037-9
published in: European Journal of Combinatorics
publication date: 1987-01-01T00:00:00Z
review text: The well-known concept of a perfect graph was introduced by Berge in the early sixties. By a critical imperfect graph G the author means a graph with the property that any proper induced subgraph of G is perfect and G itself is not perfect. He proves that a critical imperfect graph is such that each pair of different vertices is joined by an odd induced path. Then he defines a new class of perfect graphs containing two known classes of perfect graphs: perfectly orderable graphs defined by \textit{V. Chvátal} [Perfect graphs, Ann. Discrete Math. 21, 63-65 (1984; Zbl 0559.05055)] and graphs such that every odd cycle has two chords (see \textit{H. Meyniel} [Discrete Math. 16, 339-342 (1976; Zbl 0383.05018)]).
reviewed by: J.Sedláček
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 4055669
zbMATH Keywords: perfect graph
zbMATH Keywords: critical imperfect graph
zbMATH Keywords: perfectly orderable graphs
zbMATH Keywords: odd cycle
zbMATH Keywords: chords
author: Henri Meyniel
MaRDI profile type: Publication
cites work: Q3312256
cites work: Q3222875
cites work: Star-cutsets and perfect graphs
cites work: Q3347930
cites work: Transformations which Preserve Perfectness and H-Perfectness of Graphs
cites work: Weakly triangulated graphs
cites work: Alternating orientation and alternating colouration of perfect graphs
cites work: A characterization of perfect graphs
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: On the perfect graph conjecture
description: scientific article; zbMATH DE number 4055669