Paper detail

Improper Twin Edge Coloring of Graphs

Let $G$ be a graph whose each component has order at least 3. Let $s : E(G) \rightarrow \mathbb{Z}_k$ for some integer $k\geq 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) \rightarrow \mathbb{Z}_k$ defined by $c(v) = \sum_{e\in E_v} s(e) \mbox{ in } \mathbb{Z}_k,$ (where the indicated sum is computed in $\mathbb{Z}_k$ and $E_v$ 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)$. In this paper, we show that if $G$ is a graph with vertex chromatic number $χ(G)$, then $χ'_{it}(G)=χ(G)$, unless $χ(G)=2 \pmod 4$ and in this case $χ'_{it}(G)\in \{χ(G), χ(G)+1\}$. Moreover, we show that it is NP-hard to decide whether $χ'_{it}(G)=χ(G)$ or $χ'_{it}(G)=χ(G)+1$ and give some examples of perfect graph classes for which the problem is polynomial.