Abstract:
The clique-width is a measure of complexity of decomposing graphs into certain tree-like structures. The class of graphs with bounded clique-width contains bounded tree-width graphs. While there are many results on the graph isomorphism problem for bounded tree-width graphs, very little is known about isomorphism of bounded clique-width graphs. We give the first polynomial-time graph isomorphism algorithm for graphs with clique-width at most 3.