On asymmetric colourings of claw-free graph
Publikationen: Beitrag in Fachzeitschrift › Artikel › Forschung › (peer-reviewed)
Autoren
Organisationseinheiten
Externe Organisationseinheiten
- Berg- und Hüttenakademie Krakau
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 ∆(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.
Details
Originalsprache | Englisch |
---|---|
Aufsatznummer | P3.25 |
Seitenumfang | 14 |
Fachzeitschrift | Electronic Journal of Combinatorics |
Jahrgang | 28.2021 |
Ausgabenummer | 3 |
DOIs | |
Status | Veröffentlicht - 16 Juli 2021 |