Some results concerning the complexity of interval edge-colorings of graphs

The interval coloring of a weighted graph so that each edge receives a number of consecutive colors and no two colors of the edges at any vertex are the same is a generalization of the classical edge-coloring problem to graphs with integer weights on the edges. In this contribution we consider the complexity of this problem in some of its more interesting special cases. Obviously, finding of an optimal solution to interval edge-coloring problem is NP-hard, as it is already NP-complete to determine the chromatic index of a simple graph. Therefore, we assume some strong restrictions on the length of coloring intervals and the structure of a graph. In this way we obtain a number of result about special cases that are either positive (i.e. polynomially solvable subproblems) or negative (i.e. NP-completeness proofs).