Univerza na Primorskem Fakulteta za matematiko, naravoslovje in informacijske tehnologije

Raziskovalni matematični seminar - Arhiv

2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010
1 2 3 4 5 6 7 8 9 10 11 12
Datum in ura / Date and time: 18.10.19
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Monika Pilśniak (AGH University, Poland)
Naslov / Title: Asymmetric Colourings of Infinite Graphs
Vsebina / Abstract:

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.

Datum in ura / Date and time: 30.9.19
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Borut Lužar (Fakulteta za informacijske študije v Novem mestu)
Naslov / Title: Between proper and strong edge-colorings
Vsebina / Abstract:

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.