The bichromaticity of cylinder graphs and torus graphs
Dan Pritikin · Journal of Graph Theory · 1987
Abstract The bichromaticity of a bipartite graph B is defined as the maximum value of r + s for which B has the complete bipartite graph Kr, s as a homomorphic image. We determine the bichromaticity of any bipartite cylinder graph C2n × Pm or torus graph C2n × C2m. In the process, we disprove a conjecture of Harary, Hsu, and Miller [2].