A new property of critical imperfect graphs and some consequences (Q1104342): Difference between revisions

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)]).