Monika Pilsniak: On asymmetric proper colourings

Date of publication: 14. 10. 2019
Mathematics lecture
Predavanje prejemnice Nagrade Petre Šparl, v torek, 15. 10. 2019, od 11:00 do 12:00, v okviru Seminarja za disktretno matematiko, Plemljev seminar, Jadranska 19

Predavateljica:  Monika Pilsniak, AGH University, Krakow, Poljska

Monika Pilsniak je prejemnica nagrade Petre Šparl za leto 2018. Nagrado je podelila revija Ars Mathematica Contemporanea za najboljši  članek mlade matematičarke, objavljen v zadnjih petih letih. Več o nagradi na https://amc-journal.eu/index.php/amc/article/view/1709/1213.

Naslov predavanja:  On asymmetric proper colourings

Povzetek. A colouring of a graph G is called asymmetric if the identity is the only automorphism preserving the colouring. The distinguishing chromatic number D(G) of a graph G is the least number of colours in an asymmetric proper vertex colouring. This invariant was introduced by Collins and Trenk in [1], and for infinite graphs it was first investigated by Imrich, Kalinowski, Pilsniak and Shekarriz in [2]. Asymmetric proper edge colourings were first investigated by Kalinowski, Pilsniak, Przybylo and Wozniak in [3], and corresponding total colourings by Kalinowski, Pilsniak and Wozniak in [4].

In the talk, we survey results on proper asymmetric vertex and edge colourings of finite and infinite graphs. We give known general upper bounds in terms of maximum degree. We also formulate some conjectures in this topic.

[1] K. L. Collins, A. N.Trenk, The distinguishing chromatic number, Electron. J. Combin. 13 (2006), R16.
[2] W. Imrich, R. Kalinowski, M. Pilsniak, M. Shekarriz, Bounds for Distinguishing Invariants of Infinite Graphs, Electron. J. Combin. 24(3) (2017), P3.6.
[3] R. Kalinowski, M. Pilsniak, J. Przybylo, M.Wozniak, How to personalize the vertices of a graph?, European J. Combin. 40 (2014), 116-123.
[4] R. Kalinowski, M. Pilsniak, M.Wozniak, Distinguishing graphs by total colourings, Ars Math Contemp. 11 (2016), 79-89.