Name
Abstract | ||
|---|---|---|
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) <= 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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.37236/8886 | ELECTRONIC JOURNAL OF COMBINATORICS |
DocType | Volume | Issue |
Journal | 28 | 3 |
ISSN | Citations | PageRank |
1077-8926 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wilfried Imrich | 1 | 0 | 0.34 |
| Rafal Kalinowski | 2 | 0 | 0.34 |
| Monika Pilsniak | 3 | 29 | 5.42 |
| Mariusz Wozniak | 4 | 0 | 0.68 |