A generalization of perfect graphs— i ‐perfect graphs

Let i be a positive integer. We generalize the chromatic number X ( G ) of G and the clique number o( G ) of G as follows: The i‐chromatic number of G, denoted by X ( G ), is the least number k for which G has a vertex partition V 1 , V 2 ,…, V k such that the clique number of the subgraph induced by each V j , 1 ≤ j ≤ k, is at most i. The i‐clique number, denoted by o i ( G ), is the i ‐chromatic number of a largest clique in G, which equals [o( G /i]. Clearly X 1 ( G ) = X ( G ) and o 1 ( G ) = o( G ). An induced subgraph G ′ of G is an i‐transversal iff o( G′ ) = i and o( G − G ′) = o( G ) − i . We generalize the notion of perfect graphs as follows: (1) A graph G is i‐perfect iff Xi ( H ) = o i ( H ) for every induced subgraph H of G . (2) A graph G is perfectly i‐transversable iff either o( G ) ≤ i or every induced subgraph H of G with o( H ) > i contains an i ‐transversal of H . We study the relationships among i ‐perfect graphs and perfectly i ‐transversable graphs. In particular, we show that 1‐perfect graphs and perfectly 1‐transversable graphs both coincide with perfect graphs, and that perfectly i ‐transversable graphs form a strict subset of i ‐perfect graphs for every i ≥ 2. We also show that all planar graphs are i ‐perfect for every i ≥ 2 and perfectly i ‐transversable for every i ≥ 3; the latter implies a new proof that planar graphs satisfy the strong perfect graph conjecture. We prove that line graphs of all triangle‐free graphs are 2‐perfect. Furthermore, we prove for each i greater than or equal to2, that the recognition of i ‐perfect graphs and the recognition of perfectly i ‐transversable graphs are intractable and not likely to be in co‐NP. We also discuss several issues related to the strong perfect graph conjecture. © 1996 John Wiley & Sons, Inc.