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)
- Parameterized complexity of vertex deletion into perfect graph classes
- Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization
- Independence polynomials of circulants with an application to music
- Triangle-free strongly circular-perfect graphs
- On the maximum weight independent set problem in graphs without induced cycles of length at least five
- Lower bounds for kernelizations and other preprocessing procedures
- Maximum weight independent sets in hole- and co-chair-free graphs
- Injective colorings of graphs with low average degree
- Graph classes and Ramsey numbers
- Finding clubs in graph classes
- On the chromatic number of some \(P_5\)-free graphs
- Associated primes of monomial ideals and odd holes in graphs
- Well-covered circulant graphs
- On independent vertex sets in subclasses of apple-free graphs
- Combinatorial symbolic powers
- Colorings of hypergraphs, perfect graphs, and associated primes of powers of monomial ideals
- Constructions of \(k\)-critical \(P_5\)-free graphs
- A note on kernels and Sperner's Lemma
- On a conjecture concerning the Petersen graph. II
- Random threshold digraphs
- Claw-free graphs with strongly perfect complements. Fractional and integral version. I: Basic graphs
- Claw-free graphs with strongly perfect complements. Fractional and integral version. II: Nontrivial strip-structures
- Classes of graphs with small rank decompositions are \(\chi \)-bounded
- Three-colourable perfect graphs without even pairs
- Detecting 2-joins faster
- On claw-free \(t\)-perfect graphs
- Handelman's hierarchy for the maximum stable set problem
- Line-graphs of cubic graphs are normal
- On opposition graphs, coalition graphs, and bipartite permutation graphs
- On the complexity of 4-coloring graphs without long induced paths
- A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants)
- The strong perfect graph conjecture for pan-free graphs
- On the structure of certain intersection graphs
- Strongly perfect claw‐free graphs—A short proof
- Even pairs in Berge graphs
- On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
- Game-perfect graphs
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- On the commuting graph of semidihedral group
- The P versus NP-complete dichotomy of some challenging problems in graph theory
- The Induced Disjoint Paths Problem
- The structure of claw-free perfect graphs
- On classes of minimal circular-imperfect graphs
- On graphs with the smallest eigenvalue at least \(-1 - \sqrt{2} \). III
- How the proof of the strong perfect graph conjecture was found
- On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs
- A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
- Grinstead's conjecture is true for graphs with a small clique number
- Set graphs. III: Proof pearl: Claw-free graphs mirrored into transitive hereditarily finite sets
- 2-clique-bond of stable set polyhedra
- Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
- Shortest Paths between Shortest Paths and Independent Sets
- Vertex-transitive CIS graphs
- Fast Skew Partition Recognition
- Simple and three-valued simple minimum coloring games
- Complexity of coloring graphs without paths and cycles
- Characterization and recognition of some opposition and coalition graph classes
- Colouring perfect graphs with bounded clique number
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Characterization of asymmetric CKI- and KP-digraphs with covering number at most 3
- A linear time algorithm for the induced disjoint paths problem in planar graphs
- Certifying algorithms
- On the chromatic number of \((P_{5},K_{2,t})\)-free graphs
- Some new hereditary classes where graph coloring remains NP-hard
- Partitioning graphs into complete and empty graphs
- \(k\)-critical graphs in \(P_5\)-free graphs
- On 3-coloring of \((2P_4,C_5)\)-free graphs
- On 3-coloring of \((2P_4,C_5)\)-free graphs
- FindingH-partitions efficiently
- Chordless paths through three vertices
- Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors
- Fair cost allocations under conflicts - a game-theoretic point of view -
- Induced disjoint paths problem in a planar digraph
- Constructions for normal graphs and some consequences
- Some results on \(k\)-critical \(P_5\)-free graphs
- Claw-free graphs. IV: Decomposition theorem
- The Erdős-Hajnal conjecture for bull-free graphs
- A limit theorem for the Shannon capacities of odd cycles. II
- On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
- Fast recognition of doubled graphs
- Claw-free circular-perfect graphs
- Non-minimal degree-sequence-forcing triples
- Title not available (Why is that?)
- A class of perfectly contractile graphs
- Almost all webs are not rank-perfect
- Induced subgraphs of graphs with large chromatic number. I. Odd holes
- Definability in the substructure ordering of simple graphs
- On the independence polynomial of the corona of graphs
- Clique-stable set separation in perfect graphs with no balanced skew-partitions
- On graphs with no induced subdivision of \(K_4\)
- Polytopes of minimum positive semidefinite rank
- The matrix Jacobson graph of finite commutative rings
- A new characterization of perfect graphs
- Title not available (Why is that?)
- Berge trigraphs
- Envy-free pricing in multi-item markets
- Coloring perfect graphs with no balanced skew-partitions
- Tractability in constraint satisfaction problems: a survey
- Graphs with induced-saturation number zero
- Boundary properties of graphs for algorithmic graph problems
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)
