Bichromaticity of bipartite graphs

Let B be a bipartite graph with edge set E and vertex bipartition M, N. The bichromaticity β( B ) is defined as the maximum number β such that a complete bipartite graph on β vertices is obtainable from B by a sequence of identifications of vertices of M or vertices of N. Let μ = max{∣ M ∣, ∣ N ∣}. Harary, Hsu, and Miller proved that β( B ) ≥ μ + 1 and that β( T ) = μ + 1 for T an arbitrary tree. We prove that β( B ) ≤ μ + ∣ E ∣/μ yielding a simpler proof that β( T ) = μ + 1. We also characterize graphs for which K μ, 2 is obtainable by such identifications. For Q K . the graph of the K ‐dimensional cube, we obtain the inequality 2 K −1 + 2   [log   2K ]≤ β( Q K ) ≤ 2 K −1 + K , the upper bound attainable iff K is a power of 2.