publication . Article . 1972

Normal hypergraphs and the perfect graph conjecture

Lovász, L.;
Restricted
  • Published: 01 Jun 1972 Journal: Discrete Mathematics, volume 2, pages 253-267 (issn: 0012-365X, Copyright policy)
  • Publisher: Elsevier BV
Abstract
AbstractA hypergraph is called normal if the chromatic index of any partial hypergraph H′ of it coincides with the maximum valency in H′. It is proved that a hypergraph is normal iff the maximum number of disjoint hyperedges coincides with the minimum number of vertices representing the hyperedges in each partial hypergraph of it. This theorem implies the following conjecture of Berge: The complement of a perfect graph is perfect. A new proof is given for a related theorem of Berge and Las Vergnas. Finally, the results are applied on a problem of integer valued linear programming, slightly sharpening some results of Fulkerson.
Subjects
arXiv: Computer Science::Discrete MathematicsMathematics::Combinatorics
free text keywords: Theoretical Computer Science, Discrete Mathematics and Combinatorics, Strong perfect graph theorem, Perfect graph theorem, Perfect graph, Conjecture, Hypergraph, Combinatorics, Trivially perfect graph, Constraint graph, Mathematics, Discrete mathematics, Edge coloring
Related Organizations
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue