Seminár z teórie grafov - Martin Škoviera (22.10.2020)

vo štvrtok 22.10.2020 o 9:50 hod. online formou

20. 10. 2020 14.00 hod.
Od: Martin Škoviera

Prednášajúci: Martin Škoviera

Názov: Strong edge colourings of regular graphs and the covers of Kneser graphs

Termín: 22.10.2020, 9:50 hod.

Prístupový kód do MS TEAMS (pre používateľov z UK): gglxxc7
Pripojenie (pre hostí mimo UK)

Abstrakt:
A proper edge colouring of a graph is strong if it creates no bichromatic path of length three. It is well known that for a strong edge colouring of a k-regular graph at least 2k-1 colors are needed. We show that a k-regular graph admits a strong edge couloring with 2k-1 colors if and only if it covers the Kneser graph K(2k-1,k-1). In particular, a cubic graph is strongly 5-edge-colorable whenever it covers the Petersen graph.

One of the implications of this result is that a conjecture about strong edge colourings of subcubic graphs proposed by Faudree et al. [Ars Combin. 29 B (1990), 205--211] is false.

This is a joint work with Borut Lužar, Edita Máčajová and Roman Soták.