TITLE:On Recognizing Cayley Graphs AUTHORS:Lali Barrière, Pierre Fraigniaud, Cyril Gavoille, Bernard Mans and John M. Robson ABSTRACT: Given a class C of Cayley graphs, and given an edge-colored graph G of n vertices and m edges, we are interested in the problem of checking whether there exists an isomorphism $\phi$ preserving the colors such that G is isomorphic by $\phi$ to a graph in C colored by the elements of its generating set. In this paper, we give an O(m log n)-time algorithm to check whether G is color-isomorphic to a Cayley graph, improving a previous O(n4.752log n) algorithm. In the case where C is the class of the Cayley graphs defined on Abelian groups, we give an optimal O(m)-time algorithm. This algorithm can be extended to check color-isomorphism with Cayley graphs on Abelian groups of given rank. Finally, we propose an optimal O(m)-time algorithm that tests color-isomorphism between two Cayley graphs on Zn, i.e., between two circulant graphs. This latter algorithm is extended to an optimal O(n)-time algorithm that tests color-isomorphism between two Abelian Cayley graphs of bounded degree.