Complexity of the Improper Twin Edge Coloring of Graphs
Graphs and Combinatorics, cilt.33, sa.4, ss.595-615, 2017 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 33 Sayı: 4
- Basım Tarihi: 2017
- Doi Numarası: 10.1007/s00373-017-1782-7
- Dergi Adı: Graphs and Combinatorics
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.595-615
- Anahtar Kelimeler: Modular chromatic index, NP-hardness, Odd/even color classes, Twin edge/vertex coloring
- Boğaziçi Üniversitesi Adresli: Evet
Özet
Let G be a graph whose each component has order at least 3. Let s: E(G) → Zk for some integer k≥ 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) → Zk defined by c(v)=∑e∈Evs(e)inZk, (where the indicated sum is computed in Zk and Ev 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 is known that χit′(G)=χ(G), unless χ(G)≡2(mod4) and in this case χ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≥ 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+ 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) or χ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.