Chapter 3
Perfect graphs
Martin Charles Golumbic
Publisher Summary
This chapter introduces perfect graphs. ω(G), the clique number of G: the size of the largest complete subgraph of G. χ(G), the chromatic number of G: the fewest number of colors needed to properly color the vertices of G, or equivalently, the fewest number of stable sets needed to cover the vertices of G. α(G), the stability number of G: the size of the largest stable set of G. k(G), the clique cover number of G: the fewest number of complete subgraphs needed to cover the vertices of G. The intersection of a clique and a stable set of a graph G can be at most one vertex. An undirected graph G is called p-critical if it is minimally imperfect–that is, G is not perfect but every proper ...
