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 dG(x) consecutive colors, where dG(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 ≤ |V| − 1.