License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.81
URN: urn:nbn:de:0030-drops-164228
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16422/
Kiefer, Sandra ;
Neuen, Daniel
A Study of Weisfeiler-Leman Colorings on Planar Graphs
Abstract
The Weisfeiler-Leman (WL) algorithm is a combinatorial procedure that computes colorings on graphs, which can often be used to detect their (non-)isomorphism. Particularly the 1- and 2-dimensional versions 1-WL and 2-WL have received much attention, due to their numerous links to other areas of computer science.
Knowing the expressive power of a certain dimension of the algorithm usually amounts to understanding the computed colorings. An increase in the dimension leads to finer computed colorings and, thus, more graphs can be distinguished. For example, on the class of planar graphs, 3-WL solves the isomorphism problem. However, the expressive power of 2-WL on the class is poorly understood (and, in particular, it may even well be that it decides isomorphism).
In this paper, we investigate the colorings computed by 2-WL on planar graphs. Towards this end, we analyze the graphs induced by edge color classes in the graph. Based on the obtained classification, we show that for every 3-connected planar graph, it holds that: a) after coloring all pairs with their 2-WL color, the graph has fixing number 1 with respect to 1-WL, or b) there is a 2-WL-definable matching that can be used to transform the graph into a smaller one, or c) 2-WL detects a connected subgraph that is essentially the graph of a Platonic or Archimedean solid, a prism, a cycle, or a bipartite graph K_{2,?}. In particular, the graphs from case (a) are identified by 2-WL.
BibTeX - Entry
@InProceedings{kiefer_et_al:LIPIcs.ICALP.2022.81,
author = {Kiefer, Sandra and Neuen, Daniel},
title = {{A Study of Weisfeiler-Leman Colorings on Planar Graphs}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {81:1--81:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16422},
URN = {urn:nbn:de:0030-drops-164228},
doi = {10.4230/LIPIcs.ICALP.2022.81},
annote = {Keywords: Weisfeiler-Leman algorithm, planar graphs, edge-transitive graphs, fixing number}
}
|
Keywords: |
|
Weisfeiler-Leman algorithm, planar graphs, edge-transitive graphs, fixing number |
|
Collection: |
|
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
28.06.2022 |
