We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Strong edge colorings of graphs and the covers of Kneser graphs.
- Authors
Lužar, Borut; Máčajová, Edita; Škoviera, Martin; Soták, Roman
- 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 k $k$‐regular graph at least 2k−1 $2k-1$ colors are needed. We show that a k $k$‐regular graph admits a strong edge coloring with 2k−1 $2k-1$ colors if and only if it covers the Kneser graph K(2k−1,k−1) $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 colorings of subcubic graphs proposed by Faudree et al. is false.
- Subjects
GRAPH coloring; PETERSEN graphs; CHARTS, diagrams, etc.; REGULAR graphs; EDGES (Geometry)
- Publication
Journal of Graph Theory, 2022, Vol 100, Issue 4, p686
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22802