Completeness of graph isomorphism problem for bipartite graph classes

摘要

It is well known that the graph isomorphism (CI) problem is GI complete even for the bipartite graphs. Recently, it is shown that the CI problem can be solved in polynomial time for the convex graphs, which is a subclass of bipartite graphs. Chordal bipartite graphs form a well-known graph class between bipartite graphs and convex graphs. The relative complexity of the CI problem for the class is unknown. We show that the CI problem is CI complete even for the chordal bipartite graphs, which draws a line between the convex graphs and chordal bipartite graphs.