Graph Isomorphism is a very well known problem in computer science. A generic procedure for the graph isomorphism problem builds on a simple color refinement procedure given below (One dimensional Weisfeiler–Lehman Procedure)
- To begin with, all vertices have the same color.
- In each color refinement step, if two vertices $u$ and $v$ have the same color but their neighbourhood are differently coloured (counting color multiplicity), then $u$ and $v$ get fresh different colours.
Please note that for $k$-WL runs at most $|V|^k$ refinement steps. See this paper by V. Arvind
Question 1: What is the tight upper bound on the number of iterations of Weisfeiler–Lehman Procedure?
I know that if the given input graphs are regular then in a one step (one iteration) algorithm will stop. I am thinking like this there is going to be partitioning of the vertices and in each iteration a partition can only split, so in the worst case at the end I can have at most $n-2$ partitions.
Question 2 : Are there graph classes not able to distinguish by color refinement procedure other than regular non-isomorphic graphs ?