O asimetričnih barvanjih grafov z omejenimi stopnjami in neskončnim gibanjem

A vertex colouring of a graph is called asymmetric if the only automorphism which preserves it is the identity. Tucker conjectured that if every automorphism of a connected, locally finite graph moves infinitely many vertices, then there is an asymmetric colouring with 2 colours. This conjecture was recently confirmed by Babai, using the heavy machinery of the classification of finite simple groups. We make progress towards a purely combinatorial proof of this conjecture in the special case of graphs with bounded maximal degree. More precisely, using only elementary combinatorial methods, we prove that if every automorphism of a connected graph with maximal degree Δ moves infinitely many vertices, then there is an asymmetric colouring using O(sqrt(Δ) log(Δ)) colours. This is the first improvement which does not depend on the classification of finite simple groups over the trivial bound of O(Δ).