2026-07-22T14:05:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12480 2024-03-06T10:50:15Z ddc:004 open_access

The Iteration Number of Colour Refinement Kiefer, Sandra McKay, Brendan D. Colour Refinement iteration number Weisfeiler-Leman algorithm quantifier depth 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sandra Kiefer and Brendan D. McKay 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.73 urn:nbn:de:0030-drops-124801 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.73 eng https://creativecommons.org/licenses/by/3.0/legalcode