色彩细化的迭代次数（CS DM）---用户7305506

颜色细化过程及其对更高维的推广（Weisfeiler-Leman算法）是解决图形同构问题方法的核心子程序。“颜色细化”以迭代方式计算其输入图的顶点的着色。

n阶图的色求精迭代次数的一个平凡上界是n-1。我们证明这个界限很紧。更准确地说，我们通过显式构造证明了存在无穷多个图G，在这些图G上，颜色求精需要| G |-1次迭代来稳定。修改我们提出的无限族，我们证明对于每一个自然数n>=10，有n个顶点上的图，在这些顶点上颜色求精至少需要n-2次迭代才能达到稳定。

原文标题：The Iteration Number of Colour Refinement

原文：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.

原文作者：Sandra Kiefer, Brendan D. McKay

原文地址：https://arxiv.org/abs/2005.10182