On asymmetric colourings of graphs with bounded degrees and infinite motion

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