Colour refinement algorithm

In graph theory and theoretical computer science, the colour refinement algorithm also known as the naive vertex classification, or the 1-dimensional version of the Weisfeiler-Leman algorithm, is a routine used for testing whether two graphs are isomorphic. While it solves graph isomorphism on almost all graphs, there are graphs such as all regular graphs that cannot be distinguished using colour refinement.

History

The first appearance of color refinement is in Stephen H. Unger's program GIT

for graph isomorphism, where it is called the Extend method.

It was described again, immediately after, in a chemistry paper.

Description

The algorithm takes as an input a graph

G

{\displaystyle G}

with

n

{\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

λ

i

{\displaystyle \lambda _{i}}

as follows:

λ

0

{\displaystyle \lambda _{0}}

is the initial colouring. If the graph is unlabelled, the initial colouring assigns a trivial colour

λ

0

(

v

)

{\displaystyle \lambda _{0}(v)}

to each vertex

v

{\displaystyle v}

. If the graph is labelled,

λ

0

{\displaystyle \lambda _{0}}

is the label of vertex

v

{\displaystyle v}

.