| Autor: |
Lužar, Borut, Mačajová, Edita, Škoviera, Martin, Soták, Roman |
| Rok vydání: |
2021 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| DOI: |
10.1002/jgt.22802 |
| Popis: |
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$-regular graph at least $2k-1$ colors are needed. We show that a $k$-regular graph admits a strong edge coloring 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 colorings of subcubic graphs proposed by Faudree et al. [Ars Combin. 29 B (1990), 205--211] is false. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
