Asymmetric Colourings of Infinite Graphs

A colouring of a graph G is called asymmetric if the identity is the only auto-morphism preserving the colouring. The distinguishing number D(G) of a graph G is the least number of colours in an asymmetric vertex colouring. It was introduced by Albertson and Collins in [1], and was first considered for infinite graphs by Imrich, Klavžar and Trofimov in [3]. Asymmetric edge colourings were first investigated by Kalinowski and Pilśniak in [4], and for infinite graphs by Broere and Pilśniak [2]. In the talk, we survey results on asymmetric vertex and edge colourings of infinite graphs. We give known general upper bounds in terms of maximum degree. We focus mainly on several classes of graphs which need only two or three colours to break all nontrivial automorphisms. The most intriguing conjecture in this area is the Infinite Motion Conjecture posed by Thomas Tucker that every connected locally finite graph, such that every nontrivial automorphism moves infinitely many vertices, has the distinguishing number at most two. We show some very recent results obtained together with Lehner and Stawiski in this topic.

[1] M.O. Albertson, K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996), R18.

[2] I. Broere, M. Pilśniak, The Distinguishing Index of the Infinite Graphs, Electron. J. Combin. 23 (2015), P1.78.

[3] W. Imrich, S. Klavžar, V. Trofimov, Distinguishing infinite graphs, Electron. J. Combin. 14 (2007), R36.

[4] R. Kalinowski, M. Pilśniak, Distinguishing graphs by edge-colourings, European J. Combin. 45 (2015), 124–131.