Strong edge colorings of graphs and the covers of Kneser graphs
Borut Lužar, Edita Máčajová, Martin Škoviera, Roman Soták
Abstract
Abstract A proper edge coloring of a graph is strong if it creates no bichromatic path of length three. It is well known that for a strong edge coloring of a ‐regular graph at least colors are needed. We show that a ‐regular graph admits a strong edge coloring with colors if and only if it covers the Kneser graph . 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 colorings of subcubic graphs proposed by Faudree et al. is false.
Topics & Concepts
CombinatoricsMathematicsEdge coloringGraph coloringCubic graph1-planar graphGraphDiscrete mathematicsComplete coloringLine graphGraph powerVoltage graphAdvanced Graph Theory ResearchLimits and Structures in Graph TheoryGraph theory and applications