Seminar of Graph Theory - Martin Škoviera (22.10.2020)

Thursday 22.10.2020 at 9:50

20. 10. 2020 14.06 hod.
By: Martin Škoviera

Martin Škoviera:
Strong edge colourings of regular graphs and the covers of Kneser graphs

MS TEAMS code (users from Comenius University in Bratislava): gglxxc7
Link (guests outside Comenius University in Bratislava)

Abstract:
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.