@inproceedings{3626803cff174ee9a8cdc5ea82e7d90e,
title = "The iteration number of colour refinement",
abstract = "The Colour Refinement procedure and its generalisation to higher dimensions, the Weisfeiler-Leman algorithm, are central subroutines in approaches to the graph isomorphism problem. In an iterative fashion, Colour Refinement computes a colouring of the vertices of its input graph. A trivial upper bound on the iteration number of Colour Refinement on graphs of order n is n − 1. We show that this bound is tight. More precisely, we prove via explicit constructions that there are infinitely many graphs G on which Colour Refinement takes |G| − 1 iterations to stabilise. Modifying the infinite families that we present, we show that for every natural number n ≥ 10, there are graphs on n vertices on which Colour Refinement requires at least n − 2 iterations to reach stabilisation.",
keywords = "Colour Refinement, Iteration number, Quantifier depth, Weisfeiler-Leman algorithm",
author = "Sandra Kiefer and McKay, {Brendan D.}",
note = "Publisher Copyright: {\textcopyright} Sandra Kiefer and Brendan D. McKay; licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).; 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020 ; Conference date: 08-07-2020 Through 11-07-2020",
year = "2020",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.ICALP.2020.73",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Artur Czumaj and Anuj Dawar and Emanuela Merelli",
booktitle = "47th International Colloquium on Automata, Languages, and Programming, ICALP 2020",
address = "Germany",
}