Injective edge chromatic index of generalized Petersen graphs (Q2105277): Difference between revisions

A (not necessarily proper) edge-colouring of a graph \(G\), \(c: E(G)\rightarrow \{1,2\ldots, k\}\), is said to be an injective \(k\)-edge colouring if whenever \(e_{1}\), \(e_{2}\), \(e_{3}\) are consecutive edges in a path of length at least 3 or a cycle of length 3, we have \(c(e_{1}) \neq c(e_{3})\). The injective edge-chromatic index of \(G\) is the smallest \(k\) for which there exists an injective \(k\)-edge colouring and it is denoted by \(\chi_{i}^{\prime}(G)\). Proper injective edge colouring is the same thing as strong colouring. The injective edge-chromatic index of a graph with maximum degree \(\Delta\) is at most \(2(\Delta -1)^{2}\). A conjectured improvement is that for graphs with maximum degree 3, this bound implying a maximum of 8 can be replaced with a maximum of 6. The generalised Petersen graph \(P(n,k)\) has vertex set \(v_{1},\ldots, v_{n},u_{1},\ldots, u_{n}\) with \(v_{1}v_{2}\dots v_{n}v_{1}\) being an outer cycle, \(u_{i}\) being adjacent to \(u_{i+k}\) for all \(i\) (with counting done modulo \(n\)) and with \(u_{i}\) adjacent to \(v_{i}\). (The well-known Petersen graph is the case \(n=5\), \(k=2\).) The main results of the paper under review are to show that \(\chi_{i}^{\prime}(P(n,k))\leq 4\) for \(n \equiv 0\) modulo 4 and \(k\equiv 1\) modulo 2 and that \(\chi_{i}^{\prime}(P(n,k))\leq 5\) if \(n\equiv 2\) modulo 3 and \(k\equiv 2\) modulo 4. Further it is shown that (for all \(n\)) \(\chi_{i}^{\prime}(P(n,3))\leq 5\), that \(\chi_{i}^{\prime}(P(2k+1,k))\leq 5\) for \(k\geq 2\) and that \(\chi_{i}^{\prime}(P(3,1)\leq 6\), and finally that \(\chi_{i}^{\prime}(P(2k+2,k))\leq 6\) for all \(k\geq 2\). These results support the conjecture mentioned at the end of the last paragraph. Proofs basically proceed by constructing a colouring.