2026-07-22T08:36:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11904 2024-03-06T10:48:58Z ddc:004 open_access

Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm Fuhlbrück, Frank Köbler, Johannes Verbitsky, Oleg Graph Isomorphism Weisfeiler-Leman Algorithm Cai-Fürer-Immerman Graphs coherent Configurations 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 2-WL, that is, whether or not 2-WL distinguishes G from any non-isomorphic graph. In fact, we solve the 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 directed graphs of color multiplicity 4 with 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-Fürer-Immerman graphs of color multiplicity 4 distinctly appear here as a natural subclass, which demonstrates that the Cai-Fürer-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₃)-configurations in incidence geometry. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Frank Fuhlbrück and Johannes Köbler and Oleg Verbitsky 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.43 urn:nbn:de:0030-drops-119046 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.43 eng https://creativecommons.org/licenses/by/3.0/legalcode