A new property of critical imperfect graphs and some consequences
From MaRDI portal
(Redirected from Publication:1104342)
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)]).
Recommendations
Cites work
- A characterization of perfect graphs
- Alternating orientation and alternating colouration of perfect graphs
- scientific article; zbMATH DE number 3889565 (Why is no real title available?)
- scientific article; zbMATH DE number 3841894 (Why is no real title available?)
- scientific article; zbMATH DE number 3891425 (Why is no real title available?)
- Normal hypergraphs and the perfect graph conjecture
- On the perfect graph conjecture
- Star-cutsets and perfect graphs
- Transformations which Preserve Perfectness and H-Perfectness of Graphs
- Weakly triangulated graphs
Cited in
(71)- Even pairs in Berge graphs
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- Alternating orientation and alternating colouration of perfect graphs
- Perfectly orderable graphs are quasi-parity graphs: a short proof
- A new conjecture about minimal imperfect graphs
- On a conjecture of Meyniel
- Slender graphs
- Locally perfect graphs
- No antitwins in minimal imperfect graphs
- Paw-free graphs
- A fast algorithm for coloring Meyniel graphs
- Two classes of perfect graphs
- Opposition graphs are strict quasi-parity graphs
- Slim graphs
- Some properties of minimal imperfect graphs
- Even pairs in claw-free perfect graphs
- Short-chorded and perfect graphs
- On the complexity of testing for odd holes and induced odd paths
- A tree representation for \(P_ 4\)-sparse graphs
- On slim graphs, even pairs, and star-cutsets
- Even and odd pairs in comparability and in P₄-comparability graphs
- On minimal imperfect graphs without induced P₅
- On the disc-structure of perfect graphs. I: The co-paw-structure
- \(P_4\)-domination in minimal imperfect graphs
- On perfectness of sums of graphs
- Perfect graphs with no \(P_ 5\) and no \(K_ 5\)
- Even and odd pairs in linegraphs of bipartite graphs
- Quasi-parity and perfect graphs
- Path parity and perfection
- On planar perfectly contractile graphs
- Building counterexamples
- Quasi-star-cutsets and some consequences
- Polyhedral results on the stable set problem in graphs containing even or odd pairs
- Properly orderable graphs
- Optimizing weakly triangulated graphs
- About skew partitions in minimal imperfect graphs
- A transformation which preserves the clique number
- No odd pairs in minimal imperfect NP\({}_{5}\) graphs.
- On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
- Even pairs and the strong perfect graph conjecture
- On the sibling-structure of perfect graphs
- On the thinness and proper thinness of a graph
- Finding induced paths of given parity in claw-free graphs
- Classes of perfect graphs
- A class of perfectly contractile graphs
- Two-colourings that decompose perfect graphs
- A decomposition for strongly perfect graphs
- New classes of critical kernel-imperfect digraphs
- New results on minimal strongly imperfect graphs
- Perfect k‐line graphs and k‐total graphs
- Perfectly contractile diamond-free graphs
- On critically perfect graphs
- Perfect and locally perfect colorings
- Holes and dominoes in Meyniel graphs
- On Roussel-Rubio-type lemmas and their consequences
- Finding an induced path of given parity in planar graphs in polynomial time
- Skeletal graphs - a new class of perfect graphs
- Graph transformations preserving the stability number
- Graph transformations preserving the stability number
- Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
- Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
- On the structure of bull-free perfect graphs
- Preperfect graphs
- Counterexamples to three conjectures concerning perfect graphs
- Contractions in perfect graphs
- Even pairs in Berge graphs with no balanced skew-partitions
- On the thinness of trees
- Improved algorithms for perfect graphs and odd holes
- Perfectly contractile graphs
- Thinness of product graphs
- A new characterization of HH-free graphs
This page was built for publication: A new property of critical imperfect graphs and some consequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104342)
