The strong perfect graph conjecture: 40 years of attempts, and its resolution
type: Item
instance of: scholarly article
title: The strong perfect graph conjecture: 40 years of attempts, and its resolution
zbMATH Open document ID: 1191.05051
author: F. Roussel
author: Irena Rusu
author: Henri Thuillier
published in: Discrete Mathematics
publication date: 2009-12-15T00:00:00Z
Mathematics Subject Classification ID: 05C17
Mathematics Subject Classification ID: 05-02
zbMATH DE Number: 5648145
zbMATH Keywords: perfect graphs
zbMATH Keywords: partitionable graphs
zbMATH Keywords: decomposition theorems
MaRDI profile type: Publication
full work available at URL: j.disc.2009.05.024
OpenAlex ID: W2036973126
Wikidata QID: Q55966530
cites work: Q4242951
cites work: Q3286847
cites work: A note on even pairs
cites work: Q3222223
cites work: Graphical properties related to minimal imperfection
cites work: Recursive generation of partitionable graphs
cites work: Q3222886
cites work: Q3222874
cites work: Berge trigraphs
cites work: Recognizing Berge graphs
cites work: The strong perfect graph theorem
cites work: On certain polytopes associated with graphs
cites work: Star-cutsets and perfect graphs
cites work: On the strong perfect graph conjecture
cites work: Q3337488
cites work: Combinatorial designs related to the strong perfect graph conjecture
cites work: Bull-free Berge graphs are perfect
cites work: Recognizing claw-free perfect graphs
cites work: Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs
cites work: Perfect graphs, partitionable graphs and cutsets
cites work: Balanced \(0,\pm 1\) matrices. II: Recognition algorithm
cites work: Even-hole-free graphs. I: Decomposition theorem
cites work: Even-hole-free graphs part II: Recognition algorithm
cites work: Odd Hole Recognition in Graphs of Bounded Clique Size
cites work: Decomposition of balanced matrices
cites work: Square-free perfect graphs.
cites work: Testing balancedness and perfection of linear matrices
cites work: Stable set bonding in perfect graphs and parity graphs
cites work: Combinatorial optimization. Packing and covering
cites work: Compositions for perfect graphs
cites work: Complete multi-partite cutsets in minimal imperfect graphs
cites work: Decomposition of Directed Graphs
cites work: On rigid circuit graphs
cites work: Paths, Trees, and Flowers
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Q4149476
cites work: Q4521527
cites work: Transformations which Preserve Perfectness and H-Perfectness of Graphs
cites work: Anti-blocking polyhedra
cites work: Q5341588
cites work: Minimal imperfect graphs: A simple approach
cites work: Algorithms on clique separable graphs
cites work: On circular critical graphs
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Q3216686
cites work: Relaxations of vertex packing
cites work: Geometric algorithms and combinatorial optimization
cites work: Q5749319
cites work: Weakly triangulated graphs
cites work: Some properties of minimal imperfect graphs
cites work: On the divisibility of graphs
cites work: Counterexamples to three conjectures concerning perfect graphs
cites work: Even pairs and the strong perfect graph conjecture
cites work: Decomposition of perfect graphs
cites work: Q3839008
cites work: A characterization of perfect graphs
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: On the Shannon capacity of a graph
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: Split-neighbourhood graphs and the strong perfect graph conjecture
cites work: Perfect graphs with no \(P_ 5\) and no \(K_ 5\)

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Q4129482

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Q3682511

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: A new property of critical imperfect graphs and some consequences

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Perfect zero–one matrices

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Almost integral polyhedra related to certain combinatorial optimization problems

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: On recognizing integer polyhedra

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: The validity of the strong perfect-graph conjecture for \((K_4-e)\)-free graphs

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Some aspects of minimal imperfect graphs

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Q4484907

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: A semi-strong perfect graph theorem

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: About skew partitions in minimal imperfect graphs

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: HOLES AND DOMINOES IN MEYNIEL GRAPHS

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Building counterexamples

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Cutsets in perfect and minimal imperfect graphs

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Q5659563

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Q4344219

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Chair-free Berge graphs are perfect

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Q5343396

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Q4871778

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: On critical edges in minimal imperfect graphs

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: The connectivity of minimal imperfect graphs

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: On a property of the class of n-colorable graphs

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Decomposition of regular matroids

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Q3621680

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Near-perfect matrices

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: The theta body and imperfection

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Q3946199

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Uniquely colorable perfect graphs

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Coloring graphs with stable cutsets

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Coloring perfect \((K_ 4\)-e)-free graphs

The strong perfect graph conjecture: 40 years of attempts, and its resolution (cites work)
cites work: Q3686753

The strong perfect graph conjecture: 40 years of attempts, and its resolution (DBLP publication ID)
DBLP publication ID: journals/dm/RousselRT09

The strong perfect graph conjecture: 40 years of attempts, and its resolution (DOI)
DOI: 10.1016/J.DISC.2009.05.024