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 co lor i, i = 1,..., t and the edges incident with each vertex x are colo red 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 col orings and their variations. It is proved, in particular, that if a si mple 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.