# graph isomorphism

A graph isomorphism is an isomorphism between two graphs \(G\) and \(H\) meaning that there exists \(f\) a bijection between the vertexes of \(G\) and those of \(H\) such that \((u, v)\) is an edge in \(G\) if and only if \((f(u), f(v))\) is an edge in \(H\).

## Weisfeiler-Lehman algorithm

This algorithm computes an approximation of the graph isomorphism, but it has good properties on simple graph. In fact, it is more a family of algorithms parameterized by an integer \(k > 0\), each algorithm is denoted by \$k\$-WL. For \(k=1\), the algorithm performs in quasi-quadratic time. Usually, we present the algorithm for k=1 as an iterative refinement of a colorization of the graph nodes, such that the nodes having the same "neighborhood shape" are colored using the same color. When k>1, the color refinement concerns the k-tuples of nodes and the complexity is O(nk+1 log(n)).

I think that the following properties are correct:

• 1-WL is able to find the isomorphisms between the trees,
• 3-WL is able to find the isomorphisms between the planar graph.

### References

• talks by Martin Grohe at KR 2021

This post accepts webmentions. Do you have the URL to your post?

Otherwise, send your comment on my service.