A linear algorithm for finding [g, f]-colorings of partial k-trees

In an ordinary edge-coloring of a graph each color appears at each vertex v at most once. A [g, f]-coloring is a generalized edge-coloring in which ea ch color appears at each vertex v at least g(v) and at most f(v) times, whe re g(v) and f(v) are respectively nonnegative and positive integers assigne d to v. This paper gives a linear-time algorithm to find a [g, f]-coloring of a given partial k-tree using the minimum number of colors if there exist s a [g, f]-coloring.