On asymmetric colourings of claw-free graphs

Wilfried Imrich¹ ; Rafał Kalinowski² ; Monika Pilśniak³ ; Mariusz Woźniak³

¹Montanuniversität Leoben, Austria
²AGH University of Science and Technology
³AGH University of Science and Technology, Krakow, Poland

The electronic journal of combinatorics, Tome 28 (2021) no. 3

Résumé

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)\leq 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.

Détail

DOI : 10.37236/8886

Classification : 05C15, 05C25
Mots-clés : asymmetric colouring number, distinguishing number