Authors: Z. Shao, E. Zhu Title: On the star chromatic index of generalized Petersen graphs Source: Discussiones Mathematicae Graph Theory Received 24.10.2017, Revised 27.11.2018, Accepted 28.11.2018, doi: 10.7151/dmgt.2195 | |
Abstract: 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 \frac{n}{3}≡ 1 ?od 3. | |
Keywords: star edge-coloring, star chromatic index, generalized Petersen graph | |
Links: |