Paper Info
Title
The Weisfeiler-Leman algorithm and recognition of graph properties
Abstract
The k-dimensional Weisfeiler-Leman algorithm (k-WL) is a very useful combinatorial tool in graph isomorphism testing. We address the applicability of k-WL to recognition of graph properties. Let G be an input graph with n vertices. We show that, if n is prime, then vertex-transitivity of G can be seen in a straightforward way from the output of 2-WL on G and on the vertex-individualized copies of G. This is perhaps the first non-trivial example of using the Weisfeiler-Leman algorithm for recognition of a natural graph property rather than for isomorphism testing. On the other hand, we show that, if n is divisible by 16, then k-WL is unable to distinguish between vertex-transitive and non-vertex-transitive graphs with n vertices unless k = Omega(root n). Similar results are obtained for recognition of arc-transitivity. Our lower bounds are based on an analysis of the Cai-Furer-Immerman construction, which might be of independent interest. In particular, we provide sufficient conditions under which the Cai-Furer-Immerman graphs can be made colorless. (C) 2021 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2021
10.1016/j.tcs.2021.09.033
THEORETICAL COMPUTER SCIENCE
Keywords
DocType
Volume
Weisfeiler-Leman algorithm, Recognition of graph properties, Vertex-transitive graphs, Arc-transitive graphs, Coherent configurations
Journal
895
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Frank Fuhlbrück102.03
Johannes Köbler200.34
Ilia N. Ponomarenko3407.24
Oleg Verbitsky400.68