Paper Info
Title
Identifiability Of Graphs With Small Color Classes By The Weisfeiler-Leman Algorithm
Abstract
As is well known, the isomorphism problem for vertex-colored graphs with color multiplicity at most 3 is solvable by the classical two-dimensional Weisfeiler-Leman algorithm (2-WL). On the other hand, the prominent Cai-Furer-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 2-WL, that is, whether or not 2-WL distinguishes G from every nonisomorphic graph. In fact, we solve the much more general problem of recognizing whether or not a given coherent configuration of maximum fiber size 4 is separable. This extends our recognition algorithm to graphs of color multiplicity 4 with directed and colored edges. Our decision procedure is based on an explicit description of the class of graphs with color multiplicity 4 that are not identifiable by 2-WL. The Cai-Furer-Immerman graphs of color multiplicity 4 distinctly appear here as a natural subclass, which demonstrates that the Cai-Furer-Immerman construction is not ad hoc. Our classification reveals also other types of graphs that are hard for 2-WL. One of them arises from patterns known as (n(3))-configurations in incidence geometry.
Year
DOI
Venue
2021
10.1137/20M1327550
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
DocType
Volume
graph isomorphism, Weisfeiler-Leman algorithm, Cai-Furer-Immerman graphs, coherent configurations
Journal
35
Issue
ISSN
Citations 
3
0895-4801
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Frank Fuhlbrück102.03
Johannes Köbler2316.83
Oleg Verbitsky300.68