Generalized perfect graphs: Characterizations and inversion Original Research Article

Given a hereditary family of graphs P one defines the P-chromatic number of a graph G (denoted χP(G)) to be the manimum size of a partition V(G) = V1 ∪ 3· ∪ Vk such that each Vi induces in G a member of P. Define ωP(G) to equal max {χP(K)} where the maximum is taken over all cliques K in G. We say that G is χP-perfect provided χP(H) = ωP(H) for all induced subgraphs H of G and we denote the set of χP-perfect graphs by P∗. In this paper we discuss the following results: 1. (1) We give analogs of the Strong Perfect Graph Conjecture, that is, we find forbidden subgraph characterizations of P∗ for various families P. 2. (2) We show the central role played by the classes Free(Kn) = {G: ω(G) < n} in finding P∗ for all hereditary P, and give a partial characterization of (Free(Kn))∗ for n ⩾ 3. 3. (3) We consider the problem of inverting perfection: given a hereditary family Q, find all hereditary P such that P∗ = Q. We find conditions on P that are necessary and sufficient for P∗ = Q. We then apply this “inverting perfection theorem” to a number of families Q.