On the Star Chromatic Index of Generalized Petersen Graphs

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-edge-colorings. 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 n3≡1(mod3){n \over 3} \equiv 1\left( {\bmod 3} \right).