Interval cyclic edge-colorings of graphs

Abstract: A proper edge-coloring of a graph

G

with colors

1, l d o t s, t

is called an emph{interval cyclic

t

-coloring} if all colors are used, and the edges incident to each vertex

v i n V (G)

are colored by

d_{G} (v)

consecutive colors modulo

t

, where

d_{G} (v)

is the degree of a vertex

v

in

G

. A graph

G

is emph{interval cyclically colorable} if it has an interval cyclic

t

-coloring for some positive integer

t

. The set of all interval cyclically colorable graphs is denoted by

m a t h f r a k N_{c}

. For a graph

G i n m a t h f r a k N_{c}

, the least and the greatest values of

t

for which it has an interval cyclic

t

-coloring are denoted by

w_{c} (G)

and

W_{c} (G)

, respectively. In this paper we investigate some properties of interval cyclic colorings. In particular, we prove that if

G

is a triangle-free graph with at least two vertices and

G i n m a t h f r a k N_{c}

, then

W_{c} (G) l e q v e r t V (G) v e r t + D e l t a (G) - 2

. We also obtain bounds on

w_{c} (G)

and

W_{c} (G)

for various classes of graphs. Finally, we give some methods for constructing of interval cyclically non-colorable graphs.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: Interval cyclic edge-colorings of graphs