Id: arxiv/2611.18391 Url: https://arxiv.org/abs/2611.18391 Tags: cs.DM, cs.DS, math.CO Score: 0 Title: Color Refinement Distinguishes Connected Rooted Outerplanar Graphs Domain: cs.DM Source: arxiv Authors: Louann Coste, M{ó}nika Csik{ó}s, Laurent Viennot Reviews: 0 Subject: cs.DM Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-13 Page: https://delphi.science/r/arxiv/2611.18391 Color refinement, also known as the $1$-dimensional Weisfeiler-Leman algorithm ($1$-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 $1$-WL, or its higher-dimensional variant $k$-WL, identifies every graph; the least such $k$ is the WL-dimension of the class. Planar graphs have WL-dimension at most $3$ (Kiefer, Ponomarenko and Schweitzer, 2019), and whether $2$-WL already distinguishes all planar graphs is a central open problem. We bring new…