On the Weisfeiler-Leman dimension of some polyhedral graphs

Abstract

Let $m$ be a positive integer, $X$ a graph with vertex set $\hat{I}\text{c◯}$, and ${\mathrm{WL}}_m(X)$ the coloring of the Cartesian $m$-power $\hat{I}{\text{c◯}}^m$, obtained by the $m$-dimensional Weisfeiler-Leman algorithm. The $\mathrm{WL}$-dimension of the graph $X$ is defined to be the smallest $m$ for which the coloring ${\mathrm{WL}}_m(X)$ determines $X$ up to isomorphism. It is known that the $\mathrm{WL}$-dimension of any planar graph is $2$ or $3$, but no planar graph of $\mathrm{WL}$-dimension $3$ is known. We prove that the $\mathrm{WL}$-dimension of a polyhedral (i.e., $3$-connected planar) graph $X$ is at most $2$ if the color classes of the coloring ${\mathrm{WL}}_2(X)$ are the orbits of the componentwise action of the group $\mathrm{Aut}(X)$ on $\hat{I}{\text{c◯}}^2$.