2019/07/05 by Frank Fuhlbrück, Fuhlbrück, Frank, Johannes Köbler +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1907.02892
As it is well known, the isomorphism problem for vertex-colored graphs with\ncolor multiplicity at most 3 is solvable by the classical 2-dimensional\nWeisfeiler-Leman algorithm (2-WL). On the other hand, the prominent\nCai-F "urer-Immerman construction shows that even the multidimensional version\nof the algorithm does not suffice for graphs with color multiplicity 4. We give\nan efficient decision procedure that, given a graph G of color multiplicity\n4, recognizes whether or not G is identifiable by 2-WL, that is, whether or\nnot 2-WL distinguishes G from any non-isomorphic graph. In fact, we solve the\nmuch more general problem of recognizing whether or not a given coherent\nconfiguration of maximum fiber size 4 is separable. This extends our\nrecognition algorithm to graphs of color multiplicity 4 with directed and\ncolored edges.\n Our decision procedure is based on an explicit description of the class of\ngraphs with color multiplicity 4 that are not identifiable by 2-WL. The\nCai-F "urer-Immerman graphs of color multiplicity 4 distinctly appear here as a\nnatural subclass, which demonstrates that the Cai-F "urer-Immerman construction\nis not ad hoc. Our classification reveals also other types of graphs that are\nhard for 2-WL. One of them arises from patterns known as (n3)-configurations\nin incidence geometry.\n