A generalization of perfect graphs?i-perfect graphs
Leizhen Cai, Derek Gordon Corneil · Journal of Graph Theory · 1996
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 V1, V2,…, Vk such that the clique number of the subgraph induced by each Vj, 1 ≤ j ≤ k, is at most i. The i-clique number, denoted by oi(G), is the i-chromatic number of a largest clique in G, which equals [o(G/i]. Clearly X1(G) = X(G) and o1(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) = oi(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.