NP-completeness of list coloring and precoloring extension on the edges of planar graphs

摘要

In the edge precoloring extension problem, we are given a graph with some of the edges having preassigned colors, and it has to be decided whether this coloring can be extended to a proper k-edge-coloring of the graph. In list edge coloring every edge has a list of admissible colors, and the question is whether there is a proper edge coloring where every edge receives a color from its list. We show that both problems are NP-complete on (a) planar 3-regular bipartite graphs, (b) bipartite outerplanar graphs, and (c) bipartite series-parallel graphs. This improves previous results of Easton and Parker [61, and Fiala [8]. (C) 2005 Wiley Periodicals, Inc.