On asymmetric colourings of claw-free graphs
type: Item
instance of: scholarly article
title: On asymmetric colourings of claw-free graphs
zbMATH Open document ID: 1470.05059
DOI: 10.37236/8886
author: Wilfried Imrich
author: Rafał Kalinowski
author: Monika Pilśniak
author: Mariusz Woźniak
published in: The Electronic Journal of Combinatorics
publication date: 2021-08-06T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 7379548
zbMATH Keywords: asymmetric colouring number
zbMATH Keywords: distinguishing number
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.37236/8886
OpenAlex ID: W3185033389
cites work: Symmetry breaking in graphs
cites work: The distinguishing index of the Cartesian product of countable graphs
cites work: Regular orbits of permutation groups on the power set
cites work: Nordhaus-Gaddum theorem for the distinguishing chromatic number
cites work: Distinguishing graphs of maximum valence 3
cites work: Distinguishing infinite graphs
cites work: Asymmetrizing trees of maximum valence \(2^{\aleph_0}\)
cites work: Zu einem Isomorphiesatz von H. Whitney für Graphen
cites work: Distinguishing graphs by edge-colourings
cites work: Distinguishing labellings of group action on vector spaces and graphs
cites work: Breaking graph symmetries by edge colourings
cites work: On symmetries of edge and vertex colourings of graphs
cites work: Distinguishing numbers of finite 4-valent vertex-transitive graphs
cites work: Improving upper bounds for the distinguishing index
cites work: The optimal general upper bound for the distinguishing index of infinite graphs
cites work: A note on the asymptotic and computational complexity of graph distinguishability
cites work: Distinguishing maps
description: scientific article; zbMATH DE number 7379548