Injective edge chromatic index of generalized Petersen graphs (Q2105277): Difference between revisions
From MaRDI portal
Set profile property. |
Created claim: Wikidata QID (P12): Q122939914, #quickstatements; #temporary_batch_1710970253704 |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s40840-022-01442-6 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W4310489782 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q122939914 / rank | |||
Normal rank |
Revision as of 23:39, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Injective edge chromatic index of generalized Petersen graphs |
scientific article |
Statements
Injective edge chromatic index of generalized Petersen graphs (English)
0 references
8 December 2022
0 references
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.
0 references
injective edge coloring
0 references
injective edge chromatic index
0 references
generalized Petersen graph
0 references