Perfectness of normal products of graphs

Let θ(θ1) be the partition number (edge partition number) of a graph, let α be the stability number of G. Then G is perfect (θ1-perfect) if for every induced subgraph H of G, we have θ(H) = α(H) (θ1(H) = α(H)). We prove the following characterization theorem for the perfectness of the normal product of two bipartite graphs: If G1 and G2 are bipartite, then their normal product G1 · G2 is perfect iff either 1. (i) G1 or G2 is K1, n, or 2. (ii) G1 or G2 is Km, n, m, n > 1, and the other is a tree. We also obtain the following sufficient condition for the perfectness of the product graphs: If G1 and G2 are θ1-perfect, then G1 · G2 is perfect. © 1978.