On the star chromatic index of generalized Petersen graphs (Q2227104)

Let \(G\) be a graph. A proper \(\ell\)-edge coloring is a map \(c:E(G)\rightarrow\{1,\dots,\ell\}\) such that every two different incident edges \(uv\) and \(vw\) receive different colors, that is \(c(uv)\neq c(vw)\). A proper \(\ell\)-edge coloring is called a star \(\ell\)-edge coloring if edges of any \(P_r\), \(r\geq 5\), or any \(C_q\), \(q\geq 4\), receive more than two colors. The star chromatic index \(\chi^\prime_s(G)\) of \(G\) is the minimum \(\ell\) such that there exists a proper star \(\ell\)-edge coloring of \(G\). Let \(k\) and \(n\), \(n\geq 2k+1\), be two positive integers. The generalized Peterson graph \(P(n,k)\) has vertex set \[V(P(n,k))=\{v_1,\dots,v_n\}\cup\{u_1,\dots,u_n\}\] and edge set \(E(P(n,k))\) equals to \[\{v_iv_{i+1}:i\in\{1,\dots,n\}\}\cup\{v_iu_i:i\in\{1,\dots,n\}\}\cup\{u_iu_{i+k}:i\in\{1,\dots,n\}\},\] where all the operations are taken modulo \(n\). Generalized Petersen graphs are one of the most important cubic graph families. This work deals with star chromatic index of generalized Petersen graphs. They characterize those Petersen graphs for which \(\chi^\prime_s(P(n,k))=4\). This happens when \(n\) is a multiple of four and \(k\) is odd. Among others they show that they have \(\chi^\prime_s(P(n,k))=5\) for ``almost all'' of them. Among the exceptions, it is not clear weather they have a star \(5\)-edge coloring or not.