The validity of the perfect graph conjecture for K₄-free graphs

This chapter builds on results based on D.R. Fulkerson's anti-blocking polyhedral approach to perfect graphs to obtain information about critical perfect graphs and related clique-generated graphs. Fulkerson felt that a proof of the perfect graph theorem would involve exactly the kind of duality that existed in his theory of blocking and anti-blocking polyhedral. A critical perfect graph—p-critical for short—is an imperfect graph all of whose proper induced subgraphs are perfect. A p-critical graph with n vertices has exactly n cliques of size ω (G) with each vertex in ω (G) maximal cliques and has exactly n stable sets of size α (G) with each vertex in α (G) maximal stable sets. Each maximal clique intersects all but one maximal stable sets, and vice versa. If G is a pseudo-p-critical graph, each maximal clique in M (G) corresponds to a vertex of G.