# Tight upper bound on the number of iterations of Weisfeiler–Lehman Procedure (Graph isomorphism)

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 ?

• How tight a bound are you looking for? As you argue in the question, it can't be more than linear; but a path of lengh $n$ requires about $n/2$ iterations. – David Richerby Mar 25 '17 at 11:06
• it can't be more than linear say $n - c$, I am looking for largest $c$ such that for all inputs, number of iterations is $\le n - c$. – aaaa Mar 25 '17 at 12:03
• OK, but you might've already done that. I've not managed to think of anything that takes more than $n/2$. – David Richerby Mar 25 '17 at 12:38
• This seems to be a research-level question, and it isn't getting answered on Computer Science, so I am migrating to Theoretical Computer Science at the asker's request. – Gilles 'SO- stop being evil' Apr 9 '17 at 10:28
• The most comprehensive discussion seems to be arxiv.org/abs/1509.08251 but the authors focus on the total time, not the number of rounds. The class of example graphs $G_k$ might be useful. – András Salamon Apr 10 '17 at 16:27