A new property of critical imperfect graphs and some consequences
From MaRDI portal
Publication:1104342
DOI10.1016/S0195-6698(87)80037-9zbMath0647.05053MaRDI QIDQ1104342
Publication date: 1987
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Graph theory (05C99) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (63)
Perfect graphs with no \(P_ 5\) and no \(K_ 5\) ⋮ Thinness of product graphs ⋮ Alternating orientation and alternating colouration of perfect graphs ⋮ Even and odd pairs in linegraphs of bipartite 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 ⋮ Quasi-parity and perfect graphs ⋮ Path parity and perfection ⋮ Two-colourings that decompose perfect graphs ⋮ On planar perfectly contractile graphs ⋮ Locally perfect graphs ⋮ On graphs without \(P_ 5\) and \(\overline {P}_ 5\) ⋮ Paw-free graphs ⋮ Building counterexamples ⋮ A fast algorithm for coloring Meyniel graphs ⋮ Two classes of perfect graphs ⋮ Opposition graphs are strict quasi-parity graphs ⋮ Even pairs and the strong perfect graph conjecture ⋮ Slim graphs ⋮ Some properties of minimal imperfect graphs ⋮ Even pairs in claw-free perfect graphs ⋮ On the thinness and proper thinness of a graph ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ Perfect and locally perfect colorings ⋮ Finding induced paths of given parity in claw-free graphs ⋮ Classes of perfect graphs ⋮ Perfectly contractile diamond-free graphs ⋮ On critically perfect graphs ⋮ Short-chorded and perfect graphs ⋮ On the complexity of testing for odd holes and induced odd paths ⋮ A decomposition for strongly perfect graphs ⋮ A tree representation for \(P_ 4\)-sparse graphs ⋮ A new characterization of HH-free graphs ⋮ On the structure of bull-free perfect graphs ⋮ Preperfect graphs ⋮ Counterexamples to three conjectures concerning perfect graphs ⋮ On slim graphs, even pairs, and star-cutsets ⋮ On Roussel-Rubio-type lemmas and their consequences ⋮ Graph transformations preserving the stability number ⋮ On the sibling-structure of perfect graphs ⋮ Skeletal graphs - a new class of perfect graphs ⋮ Polyhedral results on the stable set problem in graphs containing even or odd pairs ⋮ Graph transformations preserving the stability number ⋮ Perfect k‐line graphs and k‐total graphs ⋮ Even pairs in Berge graphs ⋮ Properly orderable graphs ⋮ Optimizing weakly triangulated graphs ⋮ Even and odd pairs in comparability and in \(P_4\)-comparability graphs ⋮ On minimal imperfect graphs without induced \(P_5\) ⋮ On the disc-structure of perfect graphs. I: The co-paw-structure ⋮ \(P_4\)-domination in minimal imperfect graphs ⋮ The strong perfect graph conjecture: 40 years of attempts, and its resolution ⋮ On perfectness of sums of graphs ⋮ HOLES AND DOMINOES IN MEYNIEL GRAPHS ⋮ About skew partitions in minimal imperfect graphs ⋮ A transformation which preserves the clique number ⋮ No odd pairs in minimal imperfect NP\({}_{5}\) graphs. ⋮ Unnamed Item ⋮ A class of perfectly contractile graphs ⋮ Perfectly contractile graphs ⋮ Quasi-star-cutsets and some consequences
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Weakly triangulated graphs
- Alternating orientation and alternating colouration of perfect graphs
- Star-cutsets and perfect graphs
- On the perfect graph conjecture
- A characterization of perfect graphs
- Normal hypergraphs and the perfect graph conjecture
- Transformations which Preserve Perfectness and H-Perfectness of Graphs
This page was built for publication: A new property of critical imperfect graphs and some consequences
