跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.18391 · v1

Color Refinement Distinguishes Connected Rooted Outerplanar Graphs

首次提交 2026-11-14 00:34
版本更新 2026-11-14 00:34
雷达观测 2026-11-16 11:41
arXiv ↗PDF ↗

摘要

Color refinement, also known as the 11-dimensional Weisfeiler-Leman algorithm (11-WL), is a classical near-linear-time heuristic for graph isomorphism, which also captures the expressive power of message-passing graph neural networks. A long line of work asks on which graph classes 11-WL, or its higher-dimensional variant kk-WL, identifies every graph; the least such kk is the WL-dimension of the class. Planar graphs have WL-dimension at most 33 (Kiefer, Ponomarenko and Schweitzer, 2019), and whether 22-WL already distinguishes all planar graphs is a central open problem. We bring new insight on this question for outerplanar graphs, whose WL-dimension is 22. We show that color refinement, i.e. 1-WL, distinguishes connected rooted outerplanar graphs: two non-isomorphic such graphs receive different stable colorings once a single vertex, the root, is individualized. The root is necessary, as there are non-isomorphic 22-connected outerplanar graphs that color refinement does not distinguish. Our result extends to pseudo-rooted graphs, in which the stable coloring merely contains a singleton color class, and to non-connected graphs whose components all contain such a class. Consequently, the (1,1)(1,1)-WL test of Rattan and Seppelt (2023) distinguishes all outerplanar graphs. We proceed by inversion: we reconstruct a connected rooted outerplanar graph, up to isomorphism, from its color graph, the weighted quotient of the graph by its stable color classes, together with its root color. The reconstruction runs in time linear in the output size and is canonical, which yields a near-linear-time canonization algorithm for these graphs. Our main tool is a dichotomy lemma, formalized in Rocq: in a rooted outerplanar graph with an equitable coloring, every block either receives pairwise distinct colors or admits a color-preserving mirror symmetry fixing its vertex closest to the root.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-14 00:34 · 最新观测版本

Color Refinement Distinguishes Connected Rooted Outerplanar Graphs

Color refinement, also known as the 11-dimensional Weisfeiler-Leman algorithm (11-WL), is a classical near-linear-time heuristic for graph isomorphism, which also captures the expressive power of message-passing graph neural networks. A long line of work asks on which graph classes 11-WL, or its higher-dimensional variant kk-WL, identifies every graph; the least such kk is the WL-dimension of the class. Planar graphs have WL-dimension at most 33 (Kiefer, Ponomarenko and Schweitzer, 2019), and whether 22-WL already distinguishes all planar graphs is a central open problem. We bring new insight on this question for outerplanar graphs, whose WL-dimension is 22. We show that color refinement, i.e. 1-WL, distinguishes connected rooted outerplanar graphs: two non-isomorphic such graphs receive different stable colorings once a single vertex, the root, is individualized. The root is necessary, as there are non-isomorphic 22-connected outerplanar graphs that color refinement does not distinguish. Our result extends to pseudo-rooted graphs, in which the stable coloring merely contains a singleton color class, and to non-connected graphs whose components all contain such a class. Consequently, the (1,1)(1,1)-WL test of Rattan and Seppelt (2023) distinguishes all outerplanar graphs. We proceed by inversion: we reconstruct a connected rooted outerplanar graph, up to isomorphism, from its color graph, the weighted quotient of the graph by its stable color classes, together with its root color. The reconstruction runs in time linear in the output size and is canonical, which yields a near-linear-time canonization algorithm for these graphs. Our main tool is a dichotomy lemma, formalized in Rocq: in a rooted outerplanar graph with an equitable coloring, every block either receives pairwise distinct colors or admits a color-preserving mirror symmetry fixing its vertex closest to the root.

查看此版本解读 →查看此版本原文 ↗