On the Weisfeiler-Leman Dimension of Some Polyhedral Graphs

Abstract

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$.