  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. We make
progress on this conjecture in the special case of graphs with bounded maximal
degree. More precisely, we prove that if every automorphism of a connected
graph with maximal degree $\Delta$ moves infinitely many vertices, then there
is an asymmetric colouring using $\mathcal O(\sqrt \Delta \log \Delta)$
colours. This is the first improvement over the trivial bound of $\mathcal
O(\Delta)$.
