The strong perfect graph theorem
From MaRDI portal
Publication:855256
DOI10.4007/ANNALS.2006.164.51zbMATH Open1112.05042arXivmath/0212070OpenAlexW1973199140WikidataQ29028413 ScholiaQ29028413MaRDI QIDQ855256FDOQ855256
Maria Chudnovsky, Paul Seymour, Robin Thomas, Neil Robertson
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
Cited In (only showing first 100 items - show all)
- Coloring square-free Berge graphs
- On the zero-divisor graphs of finite free semilattices
- On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets
- Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs
- Lovász-Schrijver PSD-Operator on Claw-Free Graphs
- Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
- Graphs of separability at most 2
- Coloring vertices of a graph or finding a Meyniel obstruction
- On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
- On standard quadratic programs with exact and inexact doubly nonnegative relaxations
- Berge's conjecture on directed path partitions -- a survey
- Clique-perfectness of claw-free planar graphs
- On the choosability of claw-free perfect graphs
- Perfectly relating the domination, total domination, and paired domination numbers of a graph
- Partitioning a graph into disjoint cliques and a triangle-free graph
- Induced Embeddings into Hamming Graphs.
- A note on the Cornaz-Jost transformation to solve the graph coloring problem
- The linear guessing number of undirected graphs
- The external constraint 4 nonempty part sandwich problem
- Complexity of clique-coloring odd-hole-free graphs
- Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement
- Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
- Substitution and \(\chi\)-boundedness
- On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes
- Regular inference as vertex coloring
- Practical and efficient split decomposition via graph-labelled trees
- \(2K_{2}\) vertex-set partition into nonempty parts
- Lovász and Schrijver $$N_+$$-Relaxation on Web Graphs
- Excluding cycles with a fixed number of chords
- Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
- Recognizing vertex intersection graphs of paths on bounded degree trees
- Colouring clique-hypergraphs of circulant graphs
- A short proof of Guenin's characterization of weakly bipartite graphs
- On circulant thin Lehman matrices
- Independent domination in hereditary classes
- On tension-continuous mappings
- On eternal domination and Vizing-type inequalities
- Maximum weight independent sets in odd-hole-free graphs without dart or without bull
- Total domination edge critical graphs with total domination number three and many dominating pairs
- Progress on the Murty-Simon conjecture on diameter-2 critical graphs: a survey
- Graphs of Separability at Most Two: Structural Characterizations and Their Consequences
- Implosive graphs: Square-free monomials on symbolic Rees algebras
- Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs
- Minimum weighted clique cover on claw‐free perfect graphs
- On bounding the difference of the maximum degree and the clique number
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Two complexity results for the vertex coloring problem
- Combinatorial optimization with 2-joins
- Claw-free \(t\)-perfect graphs can be recognized in polynomial time
- Characterising claw-free \(t\)-perfect graphs
- Clique-perfectness of complements of line graphs
- Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
- On the structure of graphs without claw, \(4K_1\) and co-R
- Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
- Perfect zero-divisor graphs
- Perfect Digraphs
- On \(P_4\)-transversals of chordal graphs
- Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
- Chromatic number and subtrees of graphs
- Strict chordal and strict split digraphs
- Excluding paths and antipaths
- A polynomial Turing-kernel for weighted independent set in bull-free graphs
- Forbidden lifts (NP and CSP for combinatorialists)
- The price of connectivity for cycle transversals
- Split digraphs
- 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\)
- THE JACOBSON GRAPH OF COMMUTATIVE RINGS
- Combinatorial symbolic powers
- Polytopes of minimum positive semidefinite rank
- The matrix Jacobson graph of finite commutative rings
- A new characterization of perfect graphs
- 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
- Minimal classes of graphs of unbounded clique-width
- On a graph of monogenic semigroups
- On the independence numbers of the cubes of odd cycles
- Colouring, constraint satisfaction, and complexity
- The structure of bull-free graphs I -- three-edge-paths with centers and anticenters
- Title not available (Why is that?)
- Chromatic number of \(P_5\)-free graphs: Reed's conjecture
- A bipartite analogue of Dilworth's theorem
- Total chromatic number of unichord-free graphs
- \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
- Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
- Rainbow generalizations of Ramsey theory: A survey
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- On the set covering polyhedron of circulant matrices
- A tutorial on branch and cut algorithms for the maximum stable set problem
- Progress on perfect graphs
- The Erdős-Hajnal conjecture. A survey
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
Recommendations
- Title not available (Why is that?) 👍 👎
- Counterexamples to three conjectures concerning perfect graphs 👍 👎
- Title not available (Why is that?) 👍 👎
- 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 👍 👎
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)
