This article has an unclear citation style. (December 2023) |
This article may contain an excessive amount of intricate detail that may interest only a particular audience.(December 2023) |
In graph theory, the Weisfeiler Leman graph isomorphism test is a heuristic test for the existence of an isomorphism between two graphs G and H.[1] It is a generalization of the color refinement algorithm and has been first described by Weisfeiler and Leman in 1968.[2] The original formulation is based on graph canonization, a normal form for graphs, while there is also a combinatorial interpretation in the spirit of color refinement and a connection to logic.
There are several versions of the test (e.g. k-WL and k-FWL) referred to in the literature by various names, which easily leads to confusion. Additionally, Andrey Leman is spelled `Lehman' in several older articles.