Szczegóły publikacji
Opis bibliograficzny
On asymmetric colourings of claw-free graphs / Wilfried Imrich, Rafał KALINOWSKI, Monika PILŚNIAK, Mariusz WOŹNIAK // The Electronic Journal of Combinatorics [Dokument elektroniczny]. — Czasopismo elektroniczne ; ISSN 1077-8926. — 2021 — vol. 28 iss. 3 art. no. P3.25, s. 1–14. — Wymagania systemowe: Adobe Reader. — Bibliogr. s. 14, Abstr. — Publikacja dostępna online od: 2021-07-16
Autorzy (4)
- Imrich Wilfried
- AGHKalinowski Rafał
- AGHPilśniak Monika
- AGHWoźniak Mariusz
Dane bibliometryczne
| ID BaDAP | 135862 |
|---|---|
| Data dodania do BaDAP | 2021-09-07 |
| Tekst źródłowy | URL |
| DOI | 10.37236/8886 |
| Rok publikacji | 2021 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Creative Commons | |
| Czasopismo/seria | The Electronic Journal of Combinatorics |
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.