Injective edge chromatic index of generalized Petersen graphs
type: Item
instance of: scholarly article
title: Injective edge chromatic index of generalized Petersen graphs
zbMATH Open document ID: 1504.05091
author: Xiaolan Hu
author: Belayneh-Mengistu Legass
published in: Bulletin of the Malaysian Mathematical Sciences Society. Second Series
publication date: 2022-12-08T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 7628909
zbMATH Keywords: injective edge coloring
zbMATH Keywords: injective edge chromatic index
zbMATH Keywords: generalized Petersen graph
reviewed by: David B. Penman
MaRDI profile type: Publication
full work available at URL: s40840-022-01442-6
OpenAlex ID: W4310489782
Wikidata QID: Q122939914
cites work: Induced and weak induced arboricities
cites work: Injective edge coloring of graphs
cites work: Complexity and algorithms for injective edge-coloring in graphs
cites work: Injective edge-coloring of graphs with given maximum degree
cites work: Injective edge coloring of generalized Petersen graphs
cites work: Note on injective edge-coloring of graphs
cites work: Strong edge chromatic index of the generalized Petersen graphs
cites work: Note on the perfect EIC-graphs
DOI: 10.1007/S40840-022-01442-6
Recommended article: Injective edge coloring of generalized Petersen graphs
Recommended article: Q4965620
Recommended article: Strong edge chromatic index of the generalized Petersen graphs
Recommended article: On the injective chromatic number of graphs
Recommended article: Q5020302
Recommended article: Injective edge coloring of graphs
Recommended article: Q3403121
Recommended article: On injective chromatic polynomials of graphs
Recommended article: On the star chromatic index of generalized Petersen graphs
Recommended article: Some results on the injective chromatic number of graphs
description: scientific article; zbMATH DE number 7628909