The Strong Perfect Graph Theorem

Abstract

In this note, all graphs are simple (no loops or multiple edges) and finite. The vertex set of graph G is denoted by V(G) and its edge set by E(G). A stable set is a set of vertices no two of which are adjacent. A clique is a set of vertices every pair of which are adjacent. The cardinality of a largest clique in graph G is denoted by omega(G).

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 08, 2003
Accession Number
AD1021246

Entities

People

  • Gérard Cornuéjols

Organizations

  • Carnegie Mellon University

Tags

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.