Name
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 2 k - 1 $2k-1$ colors are needed. We show that a k $k$-regular graph admits a strong edge coloring with 2 k - 1 $2k-1$ colors if and only if it covers the Kneser graph K ( 2 k - 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. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1002/jgt.22802 | JOURNAL OF GRAPH THEORY |
Keywords | DocType | Volume |
covering projection, cubic graph, Kneser graph, odd graph, Petersen coloring, strong edge coloring | Journal | 100 |
Issue | ISSN | Citations |
4 | 0364-9024 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Borut Luzar | 1 | 42 | 10.86 |
| Edita Máčajová | 2 | 1 | 1.80 |
| Martin Škoviera | 3 | 427 | 54.90 |
| Roman Soták | 4 | 128 | 24.06 |