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 ...

Get Algorithmic Graph Theory and Perfect Graphs, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.