Distinguishing numbers of finite 4-valent vertex-transitive graphs

Florian Lehner, Gabriel Verret


The distinguishing number of a graph G is the smallest k such that G admits a k-colouring for which the only colour-preserving automorphism of G is the identity. We determine the distinguishing number of finite 4-valent vertex-transitive graphs. We show that, apart from one infinite family and finitely many examples, they all have distinguishing number 2.


Vertex colouring, symmetry breaking in graph, distinguishing number, vertex-transitive graphs.

Full Text:


ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications