Interval edge colorings of some products of graphs

Abstract: An edge coloring of a graph

G

with colors

1, 2, l d o t s, t

is called an interval

t

-coloring if for each

i i n 1, 2, l d o t s, t

there is at least one edge of

G

colored by

i

, and the colors of edges incident to any vertex of

G

are distinct and form an interval of integers. A graph

G

is interval colorable, if there is an integer

t g e q 1

for which

G

has an interval

t

-coloring. Let

m a t h f r a k N

be the set of all interval colorable graphs. In 2004 Kubale and Giaro showed that if

G, H i n m a t h f r a k N

, then the Cartesian product of these graphs belongs to

m a t h f r a k N

. Also, they formulated a similar problem for the lexicographic product as an open problem. In this paper we first show that if

G i n m a t h f r a k N

, then

G [n K_{1}] i n m a t h f r a k N

for any

n i n m a t h b f N

. Furthermore, we show that if

G, H i n m a t h f r a k N

and

H

is a regular graph, then strong and lexicographic products of graphs

G, H

belong to

m a t h f r a k N

. We also prove that tensor and strong tensor products of graphs

G, H

belong to

m a t h f r a k N

if

G i n m a t h f r a k N

and

H

is a regular graph.

Recommendations

Cited in

(9)

This page was built for publication: Interval edge colorings of some products of graphs