Complexity of the Improper Twin Edge Coloring of Graphs

Let G be a graph whose each component has order at least 3. Let for some integer be an improper edge coloring of G (where adjacent edges may be assigned the same color). If the induced vertex coloring defined by (where the indicated sum is computed in and 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 is known that , unless and in this case . 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 ; we call this the monotonicity property. In addition, we provide a linear time algorithm to construct an improper twin edge coloring using at most 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 or , 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.