Improper Twin Edge Coloring of Graphs

Abstract: Let

G

be a graph whose each component has order at least 3. Let

s : E (G) i g h t a r r o w m a t h b b Z_{k}

for some integer

k g e q 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) i g h t a r r o w m a t h b b Z_{k}

defined by

c (v) = s u m_{e i n E_{v}} s (e) m b o x i n m a t h b b Z_{k},

(where the indicated sum is computed in

m a t h b b 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

c h i'_{i t} (G)

. In this paper, we show that if

G

is a graph with vertex chromatic number

c h i (G)

, then

c h i'_{i t} (G) = c h i (G)

, unless

c h i (G) = 2 p m o d 4

and in this case

c h i'_{i t} (G) i n c h i (G), c h i (G) + 1

. Moreover, we show that it is NP-hard to decide whether

c h i'_{i t} (G) = c h i (G)

or

c h i'_{i t} (G) = c h i (G) + 1

and give some examples of perfect graph classes for which the problem is polynomial.

This page was built for publication: Improper Twin Edge Coloring of Graphs