On the star chromatic index of generalized Petersen graphs
Zehui Shao, Enqiang Zhu · Discussiones Mathematicae Graph Theory · 2019
The star k-edge-coloring of graph G is a proper edge coloring using k colors such that no path or cycle of length four is bichromatic. The minimum number k for which G admits a star k-edge-coloring is called the star chromatic index of G, denoted by s (G). Let GCD(n, k) be the greatest common divisor of n and k. In this paper, we give a necessary and sufficient condition of s (P (n, k)) = 4 for a generalized Petersen graph P (n, k) and show that "almost all" generalized Petersen graphs have a star 5-edgecolorings. Furthermore, for any two integers k and n ( 2k + 1) such that GCD(n, k) 3, P (n, k) has a star 5-edge-coloring, with the exception of the case that GCD(n, k) = 3, k = GCD(n, k) and n 3 1 (mod 3).