The Weisfeiler-Leman dimension of a graph , sometimes known as the WL dimension, is the smallest integer
such that the -dimensional Weisfeiler-Leman algorithm correctly identifies
(Grohe 2017).
The Weisfeiler-Leman dimension of a graph with vertex count satisfies
(Kiefer 2020, p. 37). The only graph with is the singleton
graph.
If ,
then
is the maximum over all connected components of (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 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).
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. ACM66, 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 Informatsia2,
12-16, 1968.
of a graph 
, sometimes known as the WL dimension, is the smallest integer
such that the 
-dimensional Weisfeiler-Leman algorithm correctly identifies
(Grohe 2017).
with vertex count 
satisfies
is the singleton
graph 
.
,
then 
is the maximum 
over all connected components 
of 
(Schweitzer 2018).
(Arvind et al. 2017, Schweitzer 2018, Fuhlbrück
et al. 2020).
