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 -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. [Ars Combin. 29 B (1990), 205--211] is false.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.