EUVIMEDEUVIMED entdecken
Crossref

On the Weisfeiler-Leman Dimension of Some Polyhedral Graphs

Haiyan Li, Ilia Ponomarenko, Peter Zeman

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →