The strong perfect graph theorem
From MaRDI portal
Publication:855256
DOI10.4007/ANNALS.2006.164.51zbMATH Open1112.05042arXivmath/0212070OpenAlexW1973199140WikidataQ29028413 ScholiaQ29028413MaRDI QIDQ855256FDOQ855256
Authors: Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas 
Publication date: 4 January 2007
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Abstract: A graph G is perfect if for every induced subgraph H, the chromatic number of H equals the size of the largest complete subgraph of H, and G is Berge if no induced subgraph of G is an odd cycle of length at least 5 or the complement of one. The "strong perfect graph conjecture" (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture was made recently by Conforti, Cornuejols and Vuskovic -- that every Berge graph either falls into one of a few basic classes, or it has a kind of separation that cannot occur in a minimal imperfect graph. In this paper we prove both these conjectures.
Full work available at URL: https://arxiv.org/abs/math/0212070
Recommendations
- scientific article; zbMATH DE number 4065042
- Counterexamples to three conjectures concerning perfect graphs
- scientific article; zbMATH DE number 1789914
- Progress on perfect graphs
- Berge trigraphs
- Recursive generation of partitionable graphs
- Parity graphs are kernel-M-solvable
- Two classes of perfect graphs
- Classes of perfect graphs
- Perfect graphs
Cited In (only showing first 100 items - show all)
- Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs
- Origins and genesis
- Transitive orientations in bull-reducible Berge graphs
- On Roussel-Rubio-type lemmas and their consequences
- The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
- The polynomial dichotomy for three nonempty part sandwich problems
- Perfectness of \(G\)-generalized join of graphs
- Perfect graphs, partitionable graphs and cutsets
- The weighted coloring problem for two graph classes characterized by small forbidden induced structures
- On the enhanced power graph of a finite group
- Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets
- Normal fraternally orientable graphs satisfy the strong perfect graph conjecture
- The \(\langle t \rangle \)-property of some classes of graphs
- The maximum weight stable set problem in (\(P_6\), bull)-free graphs
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- The strong perfect graph theorem
- Perfect digraphs
- An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs
- FPT and kernelization algorithms for the induced tree problem
- Triangulated neighborhoods in even-hole-free graphs
- Odd cycles and matrices with integrality properties
- Perfect graphs involving semitotal and semipaired domination
- Approximability of clique transversal in perfect graphs
- On forbidden induced subgraphs for unit disk graphs
- Matrix Partitions with Finitely Many Obstructions
- Stable skew partition problem
- Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
- \(2K_2\)-partition of some classes of graphs
- The structure of bull-free perfect graphs
- Automated generation of conjectures on forbidden subgraph characterization
- Algorithms for unipolar and generalized split graphs
- Extended skew partition problem
- A construction for non-rank facets of stable set polytopes of webs
- Vertex- and edge-minimal and locally minimal graphs
- Some properties of graphs determined by edge zeta functions
- Skew partition sandwich problem is NP-complete
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- Title not available (Why is that?)
- Bounding clique-width via perfect graphs
- Chordal probe graphs
- The polynomial dichotomy for three nonempty part sandwich problems
- Algorithms for finding an induced cycle in planar graphs
- Basic perfect graphs and their extensions
- Odd holes in bull-free graphs
- Path-bicolorable graphs
- Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
- The perfection and recognition of bull-reducible Berge graphs
- Polynomial cases for the vertex coloring problem
- Alternatives for testing total dual integrality
- The price of connectivity for cycle transversals
- Split digraphs
- On the barrier graph of an arrangement of ray sensors
- Perfect commuting graphs
- Recursive generation of partitionable graphs
- \(k\)-critical graphs in \(P_5\)-free graphs
- Graph transformations preserving the stability number
- On cd-coloring of trees and co-bipartite graphs
- Circular-imperfection of triangle-free graphs
- Title not available (Why is that?)
- Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
- On cover-structure graphs
- A magnetic procedure for the stability number
- NP-hardness of the recognition of coordinated graphs
- Algorithms on Subtree Filament Graphs
- Quasi-parity and perfect graphs
- Partial characterizations of coordinated graphs: Line graphs and complements of forests
- On the chromatic number of \(2 K_2\)-free graphs
- Characterizing and bounding the imperfection ratio for some classes of graphs
- Minimally circular-imperfect graphs with a major vertex
- Colouring of \((P_3 \cup P_2)\)-free graphs
- Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
- Some Recent Results on the Graphs of Finite-Dimensional Vector Spaces
- Chromatic bounds for some classes of \(2 K_2\)-free graphs
- On extracting maximum stable sets in perfect graphs using Lovász's theta function
- A coloring algorithm for \(4 K_1\)-free line graphs
- Precoloring extension of co-Meyniel graphs
- On coloring a class of claw-free graphs.
- On the complexity of cd-coloring of graphs
- Obstructions for three-coloring graphs without induced paths on six vertices
- The intersection of two vertex coloring problems
- Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
- On box-perfect graphs
- Decomposing Berge graphs containing no proper wheel, long prism or their complements
- Characterizations of \((4 K_1,C_4,C_5)\)-free graphs
- Duality for semiantichains and unichain coverings in products of special posets
- Vizing bound for the chromatic number on some graph classes
- A short proof of the wonderful lemma
- Claw-free circular-perfect graphs
- Coloring Artemis graphs
- Structural investigation of piecewise linearized network flow problems
- Amalgams and \(\chi\)-boundedness
- 2K2-Partition Problem
- Classes of perfect graphs
- On circular-perfect graphs: a survey
- Characterization and recognition of Helly circular-arc clique-perfect graphs
- Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time
- Universally balanced combinatorial optimization games
- Reflexive polytopes arising from perfect graphs
- The \(k\)-in-a-path problem for claw-free graphs
- The reflexive dimension of (0, 1)-polytopes
This page was built for publication: The strong perfect graph theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q855256)
