Weisfeiler-Leman 維度

圖 的 Weisfeiler-Leman 維度 ，有時也稱為 WL 維度，是最小的整數 ，使得 -維 Weisfeiler-Leman 演算法能夠正確識別 (Grohe 2017)。

頂點計數 vertex count 的圖 的 Weisfeiler-Leman 維度滿足

(Kiefer 2020, p. 37)。 唯一滿足 的圖是 單例圖 。

如果 ，則 是所有連通分量 的 的最大值 (Schweitzer 2018)。

如果一個圖的 WL 維度為 1，則它可以透過顏色細化（即，應用 1 維 WL 演算法）與每個非同構圖區分開來。 這樣的圖被稱為“已識別”（Schweitzer 2008）或“可馴服”（Arvind et al. 2015）。

WL 維度為 1 的圖已由 Arvind et al. (2015) 和 Kiefer et al. (2015) 完全（且獨立地）表徵。 不幸的是，WL 維度為 2 的圖的完整描述似乎難以處理 (Li et al. 2023)。

Weisfeiler-Leman 維度為 1 的唯一 正則圖 是雞尾酒會圖、完全圖、空圖、梯子橫檔圖和迴圈圖 (Arvind et al. 2017, Schweitzer 2018, Fuhlbrück et al. 2020)。

樹或森林的 Weisfeiler-Leman 維度為 1 (Arvind et al. 2015)，距離遺傳圖的 Weisfeiler-Leman 維度最多為 2 (Gavrilyuk et al. 2020)，平面圖的 Weisfeiler-Leman 維度最多為 3 (Kiefer et al. 2019, Li et al. 2023)。