{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-13","reactions":{}}