TOPICS
Search

Weisfeiler-Leman Dimension


The Weisfeiler-Leman dimension dim_(WL)(G) of a graph G, sometimes known as the WL dimension, is the smallest integer d such that the d-dimensional Weisfeiler-Leman algorithm correctly identifies G (Grohe 2017).

The Weisfeiler-Leman dimension of a graph G with vertex count |G|>=2 satisfies

 1<=dim_(WL)(G)<=n-1

(Kiefer 2020, p. 37). The only graph with dim_(WL)(G)=|G| is the singleton graph K_1.

If dim_(WL)(G)>=2, then dim_(WL)(G) is the maximum dim_(WL)(C) over all connected components C of G (Schweitzer 2018).

A graph has WL dimension 1 if it is distinguished from every non-isomorphic graph by color refinement (i.e., application of the 1-dimensional WL algorithm). Such a graph is said to be "identified" (Schweitzer 2008) or "amenable" (Arvind et al. 2015).

The graphs of WL-dimension 1 have been completely (and independently) characterized by Arvind et al. (2015) and Kiefer et al. (2015). Unfortunately, a complete description of the graphs of WL-dimension 2 seems intractable (Li et al. 2023).

The only regular graphs with Weisfeiler-Leman dimension 1 are the cocktail party graphs, complete graphs, empty graphs, ladder rung graphs, and the cycle graph C_5 (Arvind et al. 2017, Schweitzer 2018, Fuhlbrück et al. 2020).

The Weisfeiler-Leman dimension of a tree or forest is 1 (Arvind et al. 2015), of a distance-hereditary graph is at most 2 (Gavrilyuk et al. 2020), and of a planar graph is at most 3 (Kiefer et al. 2019, Li et al. 2023).


See also

Graph Coloring, Uniquely Colorable Graph

Explore with Wolfram|Alpha

References

Arvind, V.; Köbler, J.; Rattan, G.; and Verbitsky, O. "On the Power of Color Refinement." In Fundamentals of Computation Theory. FCT 2015 (Ed. A. Kosowski and I. Walukiewicz). Cham, Switzerland: Springer, pp. 339-350, 2015.Fuhlbrück, F.; Köbler, J.; and Verbitsky, O. "Identiability of Graphs With Small Color Classes by the Weisfeiler-Leman Algorithm." In Proc. 7th International Symposium on Theoretical Aspects of Computer Science. Germany: Dagstühl Publishing, pp. 43:1-43:18, 2020.Gavrilyuk, A. L.; Nedela, R.; and Ponomarenko, I. "The Weisfeiler-Leman Dimension of Distance-Hereditary Graphs." 24 May 2020. https://arxiv.org/abs/2005.11766.Grohe, M. Descriptive Complexity, Canonisation and Definable Graph Structure Theory. Cambridge, England: Cambridge University Press, 2017.Kiefer, S. Power and Limits of the Weisfeiler-Leman Algorithm. M.S. thesis. Aachen, Germany: RWTH Aachen University, 2020.Kiefer, S. and Neuen, D. "A Study of Weisfeiler-Leman Colorings on Planar Graphs." 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). pp. 81:1-81:20, 2022.Kiefer, S.; Ponomarenko, I.; and Schweitzer, P. "The Weisfeiler-Leman Dimension of Planar Graphs Is at Most 3." J. ACM 66, 1-31, 2019.Kiefer, S.; Schweitzer, P.; and Selman, E. "Graphs Identified by Logics With Counting." In Mathematical Foundations of Computer Science 2015. MFCS 2015 (Ed. G. Italiano, G. Pighizzini, and D. Sannella). Berlin: Springer, pp. 319-330, 2015.Li, H.; Ponomarenko, I.; and Zeman, P. "On the Weisfeiler-Leman Dimension of Some Polyhedral Graphs." 26 May 2023. https://arxiv.org/abs/2305.17302.Schweitzer, P. "The Weisfeiler-Leman Dimension of Graphs and Isomorphism Testing." Symmetry vs Regularity, 50 Years of WL. July 6, 2018. https://www.iti.zcu.cz/wl2018/pdf/wl2018_schweitzer.pdf.Weisfeiler, B. and Leman, A. "The Reduction of a Graph to Canonical Form and the Algebra Which Appears Therein." Nauchno-Technicheskaya Informatsia 2, 12-16, 1968.

Cite this as:

Weisstein, Eric W. "Weisfeiler-Leman Dimension." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Weisfeiler-LemanDimension.html

Subject classifications