ON GENERALIZED PERFECT GRAPHS - BOUNDED DEGREE AND BOUNDED EDGE PERFECTION

Given a hereditary family of graphs P one defines the P-chromatic numb er of a graph G, denoted chi(g)(G), to be the minimum size of a partit ion V(G)= V1 or...or V(k) such that each V(i) induces in G a member of P. Define omega(g) (G) to equal chi(g)(K) where K is a largest clique in G. We say that G is chi(g)-perfect provided chi(g)(H)=omega(g)(H) for all induced subgraphs H of G. We consider the properties E(t), ''h as at most t edges'' and D(t), ''has maximum degree at most t''. For t hese properties (and some variants) we prove analogues of the Strong P erfect Graph Conjecture and the Perfect Graph Theorem, and we also exh ibit polynomial time algorithms for recognizing these generalized perf ect graphs provided t>0.