 The bipartite dimension of the formula_5 lattice graph is
formula_6, if formula_7 is even and formula_8 for some integers formula_9; 
and is formula_10 otherwise .has formula_12 and the cycle formula_13 has formula_14.The computational task of determining the bipartite dimension for a given graph "G" is an optimization problem.