A bipartite graph can be labeled so all vertices of a given class are contiguous. This method does precisely that to a bipartite graph.
G = graph {{1,2},{1,4},{1,6},{3,2},{3,4},{3,6},{5,2},{5,4},{5,6}}; |
relabelBipartite G |
If any of the inputs are not bipartite graphs, then the method throws an error.