On the star chromatic index of generalized Petersen graphs
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.
- On a star chromatic index of subcubic graphs
- scientific article; zbMATH DE number 1347013
- Star chromatic index of subcubic graphs
- Star-in-coloring of cycles, generalized Petersen graphs and their middle graphs
- Star chromatic index of subcubic multigraphs
- A note on a conjecture of star chromatic index for outerplanar graphs
- Strong edge chromatic index of the generalized Petersen graphs
- Star chromatic numbers of graphs
- The star chromatic number of general Mycielski graphs of paths and cycles
- Some theorems concerning the star chromatic number of a graph
This page was built for publication: On the star chromatic index of generalized Petersen graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2227104)
