On asymmetric colourings of claw-free graphs (Q2048557)

Summary: A vertex colouring of a graph is asymmetric if it is preserved only by the identity automorphism. The minimum number of colours needed for an asymmetric colouring of a graph \(G\) is called the asymmetric colouring number or distinguishing number \(D(G)\) of \(G\). It is well known that \(D(G)\) is closely related to the least number of vertices moved by any non-identity automorphism, the so-called motion \(m(G)\) of \(G\). Large motion is usually correlated with small \(D(G)\). Recently, Babai posed the question whether there exists a function \(f(d)\) such that every connected, countable graph \(G\) with maximum degree \(\Delta(G)\leqslant d\) and motion \(m(G)>f(d)\) has an asymmetric \(2\)-colouring, with at most finitely many exceptions for every degree. We prove the following result: if \(G\) is a connected, countable graph of maximum degree at most 4, without an induced claw \(K_{1,3}\), then \(D(G)= 2\) whenever \(m(G)>2\), with three exceptional small graphs. This answers the question of Babai for \(d=4\) in the class of claw-free graphs.