A GENERALIZATION OF PERFECT GRAPHS - I-PERFECT GRAPHS

Let i be a positive integer. We generalize the chromatic number chi(G) of G and the clique number omega(G) of G as follows: The i-chromatic number of G, denoted by chi(i)(G), is the least number k for which G h as a vertex partition V-1,V-2,...,V-k such that the clique number of t he subgraph induced by each V-j, 1 less than or equal to j less than o r equal to k, is al most i. The i-clique number, denoted by omega(i)(G ), is the i-chromatic number of a largest clique in G, which equals [o mega(G)/i]. Clearly chi(1)(G) = chi(G) and omega(1)(G) = omega(G). An induced subgraph G' of G is an i-transversal iff omega(G') = i and ome ga(G - G') = omega(G) - i. We generalize the notion of perfect graphs as follows. (1) A graph G is i-perfect iff chi(i)(H) = omega(i)(H) for every induced subgraph H of G. (2) A graph G is perfectly i-transvers able iff either omega(G) less than or equal to i or every induced subg raph H of G with omega(H) > i contains an i-transversal of H. We study the relationships among i-perfect graphs and perfectly i-transversabl e graphs. In particular, we show that 1-perfect graphs and perfectly 1 -transversable graphs both coincide with perfect graphs, and that perf ectly i-transversable graphs form a strict subset of i-perfect graphs for every i greater than or equal to 2. We also show that all planar g raphs are i-perfect for every i greater than or equal to 2 and perfect ly i-transversable for every i greater than or equal to 3; the latter implies a new proof that planar graphs satisfy the strong perfect grap h conjecture. We prove that line graphs of all triangle-free graphs ar e 2-perfect. Furthermore, we prove for each i greater than or equal to 2, that the recognition of i-perfect graphs and the recognition of pe rfectly i-transversable graphs are intractable and not likely to be in co-NP. We also discuss several issues related to the strong perfect g raph conjecture. (C) 1996 John Wiley & Sons, inc.