EDGE-COLORING PARTIAL K-TREES

Many combinatorial problems can be efficiently solved for partial k-tr ees (graphs of treewidth bounded by k). The edge-coloring problem is o ne of the well-known combinatorial problems for which no efficient alg orithms were previously known, except a polynomial-time algorithm of v ery high complexity. This paper gives a linear-time sequential algorit hm and an optimal parallel algorithm which find an edge-coloring of a given partial k-tree with the minimum number of colors for fixed k. (C ) 1996 Academic Press, Inc.