A linear algorithm for finding \([g,f]\)-colorings of partial \(k\)-trees (Q1578404): Difference between revisions

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\). The 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 \(k\) and \(f\) are bounded and such a coloring exists. Recursively defined partial \(k\)-trees include trees \((k=1)\), outerplanar and series-parallel graphs \((k=2)\) and Halin graphs \((k=3)\).