An edge-coloring of a simple graph G with colors 1, 2, ..., t is called an interval t-coloring 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(sub G)(x) consecutive colors, where d(sub 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 = or
展开▼
