Complexity of the improper twin edge coloring of graphs

Abedin, P, Akbari, S, Demange, M and Ekim, T 2017, 'Complexity of the improper twin edge coloring of graphs', Graphs and Combinatorics, vol. 33, no. 4, pp. 595-615.


Document type: Journal Article
Collection: Journal Articles

Title Complexity of the improper twin edge coloring of graphs
Author(s) Abedin, P
Akbari, S
Demange, M
Ekim, T
Year 2017
Journal name Graphs and Combinatorics
Volume number 33
Issue number 4
Start page 595
End page 615
Total pages 21
Publisher Springer Japan KK
Abstract Let G be a graph whose each component has order at least 3. Let s:E(G)→Zks:E(G)→Zk for some integer k≥2k≥2 be an improper edge coloring of G (where adjacent edges may be assigned the same color). If the induced vertex coloring c:V(G)→Zkc:V(G)→Zk defined by c(v)=∑e∈Evs(e) in Zk,c(v)=∑e∈Evs(e) in Zk, (where the indicated sum is computed in ZkZk and EvEv denotes the set of all edges incident to v) results in a proper vertex coloring of G, then we refer to such a coloring as an improper twin k-edge coloring. The minimum k for which G has an improper twin k-edge coloring is called the improper twin chromatic index of G and is denoted by χ′it(G)χit′(G) . It is known that χ′it(G)=χ(G)χit′(G)=χ(G) , unless χ(G)≡2(mod4)χ(G)≡2(mod4) and in this case χ′it(G)∈{χ(G),χ(G)+1}χit′(G)∈{χ(G),χ(G)+1} . In this paper, we first give a short proof of this result and we show that if G admits an improper twin k-edge coloring for some positive integer k, then G admits an improper twin t-edge coloring for all t≥kt≥k ; we call this the monotonicity property. In addition, we provide a linear time algorithm to construct an improper twin edge coloring using at most k+1k+1 colors, whenever a k-vertex coloring is given. Then we investigate, to the best of our knowledge the first time in literature, the complexity of deciding whether χ′it(G)=χ(G)χit′(G)=χ(G) or χ′it(G)=χ(G)+1χit′(G)=χ(G)+1 , and we show that, just like in case of the edge chromatic index, it is NP-hard even in some restricted cases. Lastly, we exhibit several classes of graphs for which the problem is polynomial.
Subject Combinatorics and Discrete Mathematics (excl. Physical Combinatorics)
Analysis of Algorithms and Complexity
Applied Discrete Mathematics
Keyword(s) Modular chromatic index
Twin edge/vertex coloring
Odd/even color classes
NP-hardness
DOI - identifier 10.1007/s00373-017-1782-7
Copyright notice © Springer Japan 2017
ISSN 0911-0119
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 0 times in Scopus Article
Altmetric details:
Access Statistics: 8 Abstract Views  -  Detailed Statistics
Created: Thu, 31 Jan 2019, 11:26:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us