ISSN:
1432-0541
Keywords:
Key words. Edge-coloring, [g,f] -Coloring, Partial k -tree, Bounded treewidth, Linear-time algorithm.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. 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 each color appears at each vertex v at least g(v) and at most f(v) times, where g(v) and f(v) are respectively nonnegative and positive integers assigned 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 exists a [g,f] -coloring.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004530010017
Permalink