Seminar of Graph Theory - Martin Škoviera (22.10.2020)
Thursday 22.10.2020 at 9:50
By: 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)
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.