The strong perfect graph conjecture: 40 years of attempts, and its resolution
From MaRDI portal
Publication:1045106
DOI10.1016/j.disc.2009.05.024zbMath1191.05051OpenAlexW2036973126WikidataQ55966530 ScholiaQ55966530MaRDI QIDQ1045106
F. Roussel, Irena Rusu, Henri Thuillier
Publication date: 15 December 2009
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2009.05.024
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Perfect graphs (05C17)
Related Items
Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs ⋮ On some graph classes related to perfect graphs: a survey ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs ⋮ Split digraphs
Cites Work
- Counterexamples to three conjectures concerning perfect graphs
- Testing balancedness and perfection of linear matrices
- Perfect graphs, partitionable graphs and cutsets
- The validity of the strong perfect-graph conjecture for \((K_4-e)\)-free graphs
- On rigid circuit graphs
- On circular critical graphs
- Weakly triangulated graphs
- The strong perfect graph theorem
- Coloring perfect \((K_ 4\)-e)-free graphs
- Decomposition of perfect graphs
- Relaxations of vertex packing
- Bull-free Berge graphs are perfect
- A semi-strong perfect graph theorem
- A new property of critical imperfect graphs and some consequences
- Recognizing claw-free perfect graphs
- Star-cutsets and perfect graphs
- Some properties of minimal imperfect graphs
- Graphical properties related to minimal imperfection
- Decomposition of regular matroids
- The ellipsoid method and its consequences in combinatorial optimization
- Coloring graphs with stable cutsets
- Geometric algorithms and combinatorial optimization
- The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
- Almost integral polyhedra related to certain combinatorial optimization problems
- Algorithms on clique separable graphs
- Combinatorial designs related to the strong perfect graph conjecture
- Stable set bonding in perfect graphs and parity graphs
- Complete multi-partite cutsets in minimal imperfect graphs
- Near-perfect matrices
- Perfect graphs with no \(P_ 5\) and no \(K_ 5\)
- Building counterexamples
- Chair-free Berge graphs are perfect
- On certain polytopes associated with graphs
- Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs
- Square-free perfect graphs.
- Decomposition of balanced matrices
- Uniquely colorable perfect graphs
- Balanced \(0,\pm 1\) matrices. II: Recognition algorithm
- About skew partitions in minimal imperfect graphs
- Split-neighbourhood graphs and the strong perfect graph conjecture
- Even pairs and the strong perfect graph conjecture
- On critical edges in minimal imperfect graphs
- Minimal imperfect graphs: A simple approach
- Compositions for perfect graphs
- Recognizing Berge graphs
- Anti-blocking polyhedra
- A characterization of perfect graphs
- Normal hypergraphs and the perfect graph conjecture
- On a property of the class of n-colorable graphs
- On recognizing integer polyhedra
- Combinatorial Optimization
- Even-hole-free graphs part I: Decomposition theorem
- Even-hole-free graphs part II: Recognition algorithm
- Decomposition of Directed Graphs
- Transformations which Preserve Perfectness and H-Perfectness of Graphs
- Cones of Matrices and Set-Functions and 0–1 Optimization
- On the Shannon capacity of a graph
- Perfect zero–one matrices
- Recursive generation of partitionable graphs
- The connectivity of minimal imperfect graphs
- HOLES AND DOMINOES IN MEYNIEL GRAPHS
- Paths, Trees, and Flowers
- Odd Hole Recognition in Graphs of Bounded Clique Size
- Berge trigraphs
- Maximum matching and a polyhedron with 0,1-vertices
- A note on even pairs
- On the strong perfect graph conjecture
- On the divisibility of graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
