Speaker
Florian Lehner
(TU Graz)
Description
Call a colouring of a graph distinguishing if it is only preserved by the identity automorphism. Tucker conjectured that there is a distinguishing 2-colouring, if every non-trivial automorphism of a graph moves infinitely many vertices. While the general conjecture is still wide open, the statement is known to be true for many special graph classes. It also compares to a result for finite graphs: If every non-trivial automorphism moves at least 2log(|AutG|) vertices, then there is a distinguishing 2-colouring. We give an overview of recent progress towards Tucker’s conjecture, show how probabilistic methods can be used to simplify many proofs, and highlight some open research problems.
Primary author
Florian Lehner
(TU Graz)
