On the Weisfeiler-Leman Dimension of Some Polyhedral Graphs

Let m be a positive integer, X a graph with vertex set~Ω, and WLₘ(X) the coloring of the Cartesian m-power~Ωᵐ, obtained by the m-dimensional Weisfeiler-Leman algorithm. The WL-dimension of the graph~X is defined to be the smallest m for which the coloring WLₘ(X) determines~X up to isomorphism. It is known that the WL-dimension of any planar graph is~$2$ or~$3$, but no planar graph of WL-dimension~$3$ is known. We prove that the WL-dimension of a polyhedral (i.e., $3$-connected planar) graph~X is at most~$2$ if the color classes of the coloring WL₂(X) are the orbits of the componentwise action of the group Aut(X) on~Ω².