On the Weisfeiler-Leman dimension of some polyhedral graphs

2023/05/26 by Li, Haiyan, Ponomarenko, Ilia, Zeman, Peter
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2305.17302

Abstract

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

Related

• A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus
• A Study of Weisfeiler-Leman Colorings on Planar Graphs
• An Upper Bound on the Weisfeiler-Leman Dimension
• On the WL-dimension of circulant graphs of prime power order
• On the Weisfeiler-Leman dimension of circulant graphs