Preskoči na glavno vsebino

Monika Pilsniak: On asymmetric proper colourings

Datum objave: 13. 10. 2019
Seminar za diskretno matematiko
Torek, 15. 10. 2019, od 11h do 12h, Plemljev seminar, Jadranska 19

Pozor: seminar se začne ob 11:00.

 

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.