I have a bipartite graph, including V1 and V2 vertices, and I would like to convert it to a canonical form. One simple method is converting this graph to a general graph by expanding its adjacency matrix such that the number of rows and columns in the result matrix is equal to |V1| + |V2| and then obtain its canonical form by well-known algorithms like nauty or bliss.


However, it is not my favorite. I would like a canonical form that the permutation does not mix V1 and V2 with each other. I mean to obtain the canonical form, I am allowed to just swap labels of two vertices that both are in either V1 or V2.


I have searched about it several days, but I have not yet found anything. If you have any information, it would be nice of you to share with me.



Canonical form for a bipartite graph
Since you seem to be asking about how to compute it, I'll answer that. With nauty, bliss, Traces, etc, you can specify vertex colours then the canonical form won't mix the colours up. Just use one colour for V1 and one colour for V2.


