Ingraph theory andtheoretical computer science, thecolour refinement algorithm also known as thenaive vertex classification, or the1-dimensional version of theWeisfeiler-Leman algorithm, is a routine used for testing whether two graphs areisomorphic.^[1] While it solves graph isomorphism on almost all graphs, there are graphs such as all regular graphs that cannot be distinguished using colour refinement.

The algorithm takes as an input a graph${\displaystyle G}$ with${\displaystyle n}$ vertices. It proceeds in iterations and in each iteration produces a new colouring of the vertices. Formally a "colouring" is a function from the vertices of this graph into some set (of "colours"). In each iteration, we define a sequence of vertex colourings${\displaystyle {\lambda }_i}$ as follows:

• ${\displaystyle {\lambda }_0}$ is the initial colouring. If the graph is unlabelled, the initial colouring assigns a trivial colour${\displaystyle {\lambda }_0(v)}$ to each vertex${\displaystyle v}$. If the graph is labelled,${\displaystyle {\lambda }_0}$ is the label of vertex${\displaystyle v}$.
• For all vertices${\displaystyle v}$, we set${\displaystyle {\lambda }_{i+1}(v)=\left({\lambda }_i(v),\{\{{\lambda }_i(w)\mid w\text{ is a neighbor of }v\}\}\right)}$.

In other words, the new colour of the vertex${\displaystyle v}$ is the pair formed from the previous colour and themultiset of the colours of its neighbours.This algorithm keeps refining the current colouring. At some point it stabilises, i.e.,${\displaystyle {\lambda }_{i+1}(u)={\lambda }_{i+1}(v)}$ if and only if${\displaystyle {\lambda }_i(u)={\lambda }_i(v)}$. This final colouring is called thestable colouring.

Colour refinement can be used as a subroutine for an importantcomputational problem:graph isomorphism. In this problem we have as input two graphs${\displaystyle G,H}$ and our task is to determine whether they areisomorphic. Informally, this means that the two graphs are the same up to relabelling of vertices.

To test if${\displaystyle G}$ and${\displaystyle H}$ are isomorphic we could try the following. Run colour refinement on both graphs. If the stable colourings produced are different we know that the two graphs are not isomorphic. However, it could be that the same stable colouring is produced despite the two graphs not being isomorphic; see below.

It is easy to see that if colour refinement is given a${\displaystyle n}$ vertex graph as input, a stable colouring is produced after at most${\displaystyle n-1}$ iterations. Conversely, there exist graphs where this bound is realised.^[2] This leads to a${\displaystyle O((n+m)\log n)}$ implementation where${\displaystyle n}$ is the number of vertices and${\displaystyle m}$ the number of edges.^[3] This complexity has been proven to be optimal under reasonable assumptions.^[4]

We say that two graphs${\displaystyle G}$ and${\displaystyle H}$ aredistinguished by colour refinement if the algorithm yields a different output on${\displaystyle G}$ as on${\displaystyle H}$. There are simple examples of graphs that are not distinguished by colour refinement. For example, it does not distinguish a cycle of length 6 from a pair of triangles (example V.1 in^[5]). Despite this, the algorithm is very powerful in that arandom graph will be identified by the algorithm asymptotically almost surely.^[6] Even stronger, it has been shown that as${\displaystyle n}$ increases, the proportion of graphs that arenot identified by colour refinement decreases exponentially in order${\displaystyle n}$.^[7]

For two graphs${\displaystyle G}$ and${\displaystyle H}$, the following conditions are equivalent:

• ${\displaystyle G}$ and${\displaystyle H}$ are indistinguishable by colour refinement.
• ${\displaystyle G}$ and${\displaystyle H}$ arefractionally isomorphic.^[8][9]
• ${\displaystyle G}$ and${\displaystyle H}$ have a common coarsestequitable partition.
• ${\displaystyle G}$ and${\displaystyle H}$ have the sameuniversal cover.^[10]
• For alltrees${\displaystyle T}$, there are an equal number ofhomomorphisms from${\displaystyle T}$ to${\displaystyle G}$ as there are from${\displaystyle T}$ to${\displaystyle H}$.^[11]
• ${\displaystyle G}$ and${\displaystyle H}$ cannot be distinguished by thetwo variable fragment of first order logic withcounting.^[12]

This section is empty. You can help byadding to it.(September 2022)

• Graph algorithms

• Articles to be expanded from September 2022
• All articles to be expanded
• Articles with empty sections from September 2022
• All articles with empty sections