论文标题
改进的迭代数量
The Iteration Number of Colour Refinement
论文作者
论文摘要
颜色完善过程及其对更高维度的概括，Weisfeiler-Leman算法是图形同构问题方法中的中心子例程。以迭代方式，颜色精致计算其输入图顶点的着色。 在命令n的图表上，彩色细化的迭代数量的微不足道的上限为n-1。我们证明了这一界限很紧。更确切地说，我们通过显式结构证明，有许多图形g在哪些图上进行了颜色细化| g | -1迭代以稳定。为了修改我们提出的无限家庭，我们表明，对于每个自然数字n = 10，在n个顶点上都有图形，颜色细化至少需要N-2迭代才能达到稳定。
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.
