A new property of critical imperfect graphs and some consequences

From MaRDI portal
Publication:1104342

DOI10.1016/S0195-6698(87)80037-9zbMath0647.05053MaRDI QIDQ1104342

Henri Meyniel

Publication date: 1987

Published in: European Journal of Combinatorics (Search for Journal in Brave)




Related Items (63)

Perfect graphs with no \(P_ 5\) and no \(K_ 5\)Thinness of product graphsAlternating orientation and alternating colouration of perfect graphsEven and odd pairs in linegraphs of bipartite graphsPerfectly orderable graphs are quasi-parity graphs: a short proofA new conjecture about minimal imperfect graphsOn a conjecture of MeynielSlender graphsQuasi-parity and perfect graphsPath parity and perfectionTwo-colourings that decompose perfect graphsOn planar perfectly contractile graphsLocally perfect graphsOn graphs without \(P_ 5\) and \(\overline {P}_ 5\)Paw-free graphsBuilding counterexamplesA fast algorithm for coloring Meyniel graphsTwo classes of perfect graphsOpposition graphs are strict quasi-parity graphsEven pairs and the strong perfect graph conjectureSlim graphsSome properties of minimal imperfect graphsEven pairs in claw-free perfect graphsOn the thinness and proper thinness of a graphIntersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphsPerfect and locally perfect coloringsFinding induced paths of given parity in claw-free graphsClasses of perfect graphsPerfectly contractile diamond-free graphsOn critically perfect graphsShort-chorded and perfect graphsOn the complexity of testing for odd holes and induced odd pathsA decomposition for strongly perfect graphsA tree representation for \(P_ 4\)-sparse graphsA new characterization of HH-free graphsOn the structure of bull-free perfect graphsPreperfect graphsCounterexamples to three conjectures concerning perfect graphsOn slim graphs, even pairs, and star-cutsetsOn Roussel-Rubio-type lemmas and their consequencesGraph transformations preserving the stability numberOn the sibling-structure of perfect graphsSkeletal graphs - a new class of perfect graphsPolyhedral results on the stable set problem in graphs containing even or odd pairsGraph transformations preserving the stability numberPerfect k‐line graphs and k‐total graphsEven pairs in Berge graphsProperly orderable graphsOptimizing weakly triangulated graphsEven and odd pairs in comparability and in \(P_4\)-comparability graphsOn 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 graphsThe strong perfect graph conjecture: 40 years of attempts, and its resolutionOn perfectness of sums of graphsHOLES AND DOMINOES IN MEYNIEL GRAPHSAbout skew partitions in minimal imperfect graphsA transformation which preserves the clique numberNo odd pairs in minimal imperfect NP\({}_{5}\) graphs.Unnamed ItemA class of perfectly contractile graphsPerfectly contractile graphsQuasi-star-cutsets and some consequences



Cites Work


This page was built for publication: A new property of critical imperfect graphs and some consequences