Seminar of Graph Theory - Roman Nedela (24.11.2016)
Thursday 24.11.2016 at 9:50, Lecture room M/213
Roman Nedela (University of West Bohemia, Pilsen):
Cayley recognition problem for graphs on 4p vertices
Abstract:
In the context of several algorithmic problems, we shall discuss results about the complexity of the Cayley recognition and the Cayley isomorphism problems. We shall present a new result, done in the collaboration with I. Ponomarenko, that for graphs on 4p vertices these problems can be solved in a polynomial time. In our proof, as is the case also in the recent Babai's result on the complexity of the graph isomorphism problem, the Weisfeiler- Leman stabilisation algorithm producing the smallest coherent algebra for a prescribed set of integer matrices plays an important role.