Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm

Frank Fuhlbrück, Johannes Köbler & Oleg Verbitsky
It is well known that the isomorphism problem for vertex-colored graphs with color multiplicity at most 3 is solvable by the classical 2-dimensional Weisfeiler-Leman algorithm (2-WL). On the other hand, the prominent Cai-Fürer-Immerman construction shows that even the multidimensional version of the algorithm does not suffice for graphs with color multiplicity 4. We give an efficient decision procedure that, given a graph G of color multiplicity 4, recognizes whether or not G is identifiable by...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.