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