 # 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 Journal Articles

Title Complexity of the improper twin edge coloring of graphs Abedin, P Akbari, S Demange, M Ekim, T 2017 Graphs and Combinatorics 33 4 595 615 21 Springer Japan KK 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. Combinatorics and Discrete Mathematics (excl. Physical Combinatorics) Analysis of Algorithms and Complexity Applied Discrete Mathematics Modular chromatic index Twin edge/vertex coloring Odd/even color classes NP-hardness 10.1007/s00373-017-1782-7 © Springer Japan 2017 0911-0119
 Versions Version Filter Type Thu, 31 Jan 2019, 13:43:29 EST Filtered Full
Citation counts: Cited 0 times in Thomson Reuters Web of Science Article Cited 0 times in Scopus Article 17 Abstract Views  -  Detailed Statistics Thu, 31 Jan 2019, 11:26:00 EST by Catalyst Administrator