INVESTIGATION ON INTERVAL EDGE-COLORINGS OF GRAPHS

An edge-coloring of a simple graph G with colors 1, 2,..., t is called an interval t-coloring [3] if at least one edge of G is colored by color i, i = 1,..., t and the edges incident with each vertex x are colored by d(G)(x) consecutive colors, where d(G)(x) is the degree of the vertex x. In this paper we investigate some properties of interval colorings and their variations. It is proved, in particular, that if a simple graph G=(V, E) without triangles has an interval t-coloring, then t less than or equal to\V\-1. (C) 1994 Academic Press, Inc.