On asymmetric colourings of claw-free graph
Research output: Contribution to journal › Article › Research › peer-review
Standard
In: Electronic Journal of Combinatorics, Vol. 28.2021, No. 3, P3.25, 16.07.2021.
Research output: Contribution to journal › Article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex - Download
}
RIS (suitable for import to EndNote) - Download
TY - JOUR
T1 - On asymmetric colourings of claw-free graph
AU - Imrich, Wilfried
AU - Kalinowski, Rafal
AU - Pilśniak, Monika
AU - Woźniak, Mariusz
N1 - Publisher Copyright: © The authors. Released under the CC BY-ND license (International 4.0).
PY - 2021/7/16
Y1 - 2021/7/16
N2 - 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 ∆(G) 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 K1,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.
AB - 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 ∆(G) 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 K1,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.
UR - http://www.scopus.com/inward/record.url?scp=85110712632&partnerID=8YFLogxK
U2 - 10.37236/8886
DO - 10.37236/8886
M3 - Article
AN - SCOPUS:85110712632
VL - 28.2021
JO - Electronic Journal of Combinatorics
JF - Electronic Journal of Combinatorics
SN - 1077-8926
IS - 3
M1 - P3.25
ER -