On the Weisfeiler-Leman Dimension of Some Polyhedral Graphs
The Electronic Journal of Combinatorics · 07.08.2026 · 33 (3)
DOI: 10.37236/13936 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 07.08.2026. Verfasst von Haiyan Li und 2 weiteren Autor:innen.
Abstract (Originalsprache)
Let $m$ be a positive integer, $X$ a graph with vertex set~$\Omega$, and $\text{WL}_m(X)$ the coloring of the Cartesian $m$-power~$\Omega^m$, obtained by the $m$-dimensional Weisfeiler-Leman algorithm. The $\text{WL}$-dimension of the graph~$X$ is defined to be the smallest $m$ for which the coloring $\text{WL}_m(X)$ determines~$X$ up to isomorphism. It is known that the $\text{WL}$-dimension of any planar graph is~$2$ or~$3$, but no planar graph of $\text{WL}$-dimension~$3$ is known. We prove that the $\text{WL}$-dimension of a polyhedral (i.e., $3$-connected planar) graph~$X$ is at most~$2$ if the color classes of the coloring $\text{WL}_2(X)$ are the orbits of the componentwise action of the group $\text{Aut}(X)$ on~$\Omega^2$.
Zitieren
APA
Li, H., Ponomarenko, I., & Zeman, P. (2026). On the Weisfeiler-Leman Dimension of Some Polyhedral Graphs. The Electronic Journal of Combinatorics, 33(3). https://doi.org/10.37236/13936
Vancouver
Li H, Ponomarenko I, Zeman P. On the Weisfeiler-Leman Dimension of Some Polyhedral Graphs. The Electronic Journal of Combinatorics. 2026;33(3). doi:10.37236/13936
BibTeX
@article{Li2026,
author = {Li, Haiyan and Ponomarenko, Ilia and Zeman, Peter},
title = {On the Weisfeiler-Leman Dimension of Some Polyhedral Graphs},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {3},
doi = {10.37236/13936}
}
EUVIMED