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:
PDF