Raziskovalni matematični seminar - Arhiv

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.

In the talk, we will discuss edge-colorings of (sub)cubic graphs. Namely, we will consider edge-colorings in which we work with two types of colors: the proper and the strong colors. The edges colored with the same proper color form a matching (no two edges are incident), and the edges colored with the same strong color form an induced matching (no two edges are incident to a common edge). Clearly, when all the colors are proper, the edge-coloring of a graph is proper, and if all the colors are required to be strong, we have a strong edge-coloring. The tight upper bounds for the chromatic indices of the above two extremal colorings are long established, thus we will focus to edge-colorings with combinations of proper and strong colors. Such colorings have been investigated before, but only as a tool to obtain results for other types of colorings. Systematically, they have been introduced just recently by Gastineau and Togni as the edge coloring variation of S-packing colorings. We will present results on the topic and give a number of open problems.