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)。