Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.73
URN: urn:nbn:de:0030-drops-124801
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12480/
Kiefer, Sandra ; McKay, Brendan D.
The Iteration Number of Colour Refinement
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{kiefer_et_al:LIPIcs:2020:12480,
author = {Sandra Kiefer and Brendan D. McKay},
title = {{The Iteration Number of Colour Refinement}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {73:1--73:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-138-2},
ISSN = {1868-8969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12480},
URN = {urn:nbn:de:0030-drops-124801},
doi = {10.4230/LIPIcs.ICALP.2020.73},
annote = {Keywords: Colour Refinement, iteration number, Weisfeiler-Leman algorithm, quantifier depth}
}
| Keywords: | Colour Refinement, iteration number, Weisfeiler-Leman algorithm, quantifier depth | |
| Seminar: | 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 29.06.2020 |
