Homomorphisms of finite bipartite graphs onto complete bipartite graphs

In [1] F. H a r a r y, D. Hsu and Z. Mi l le r have introduced the concepts of a bicomplete homomorphism and bichromaticity of a bipartite graph. Let B be a connected bipartite graph on the vertex sets C, D. A bicomplete homomorphism of B is a homomorphic mapping tp of B onto a complete bipartite graph K,., (where r, s are positive integers) with the property that tp(x) = q>(y) only if either both x, y belong to C, or both x, y belong to D. The bichromaticity P(B) of the graph B is the maximum value of r + s for all complete bipartite graphs K,., onto which B can be mapped by a bicomplete homomorphism. (In [1] only finite graphs are considered.) In [4] an analogous concept was introduced and studied for infinite graphs. In the present paper we shall study it for finite graphs. For a connected bipartite graph B the symbol Po(B) denotes the supremum of the values min (r, s) for all complete bipartite graphs K,., (where r, s are positive integers or infinite cardinal numbers) onto which B can be mapped by a bicomplete homomorphism. This definition was so formulated in order that it might have