On asymmetric colourings of claw-free graphs
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.
- A note on the asymptotic and computational complexity of graph distinguishability
- Asymmetrizing trees of maximum valence \(2^{\aleph_0}\)
- Breaking graph symmetries by edge colourings
- Distinguishing graphs by edge-colourings
- Distinguishing graphs of maximum valence 3
- Distinguishing infinite graphs
- Distinguishing labellings of group action on vector spaces and graphs
- Distinguishing maps
- Distinguishing numbers of finite 4-valent vertex-transitive graphs
- Improving upper bounds for the distinguishing index
- Nordhaus-Gaddum theorem for the distinguishing chromatic number
- On symmetries of edge and vertex colourings of graphs
- Regular orbits of permutation groups on the power set
- Symmetry breaking in graphs
- The distinguishing index of the Cartesian product of countable graphs
- The optimal general upper bound for the distinguishing index of infinite graphs
- Zu einem Isomorphiesatz von H. Whitney für Graphen
This page was built for publication: On asymmetric colourings of claw-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2048557)
