Breaking graph symmetries by edge colourings

الأصل · EN

The distinguishing index D'(G) of a graph G is the least number of colours needed in an edge colouring which is not preserved by any non-trivial automorphism. Broere and Pilśniak conjectured that if every non-trivial automorphism of a countable graph G moves infinitely many edges, then D'(G) ≤ 2. We prove this conjecture.