文章基本信息

标题：The Iteration Number of Colour Refinement
本地全文：下载
作者：Sandra Kiefer ; Brendan D. McKay
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：73:1-73:19
DOI：10.4230/LIPIcs.ICALP.2020.73
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Colour Refinement; iteration number; Weisfeiler-Leman algorithm; quantifier depth