Algebra seminar in Lincoln on 12 October 2016: talk by Dr Florian Lehner

Florian Lehner (University of Hamburg) will speak at the Algebra seminar on Wednesday,  12 October 2016, at 16:30, room JBL0C05 (bldg. 22 on University of Lincoln campus map). He will speak about “Breaking graph symmetries by edge colourings”.

Abstract: An (edge or vertex) colouring of a graph is said to be distinguishing, if it is not preserved by any automorphism apart from the identity. Tucker conjectured that if every automorphism of an infinite locally finite graph moves infinitely many vertices, then there is a distinguishing vertex colouring with 2 colours. While this conjecture has been verified in many special cases it is still wide open in its full generality. Recently, Pilsniak and Broere proposed an analogous conjecture for edge colourings. We prove this conjecture which also implies Tucker’s conjecture for line graphs. We also indicate, why the problem of finding a distinguishing colouring is probably easier for edge colourings than for vertex colourings.