Premium
NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
Author(s) -
Marx Dániel
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20085
Subject(s) - combinatorics , edge coloring , mathematics , bipartite graph , list coloring , planar graph , graph coloring , 1 planar graph , discrete mathematics , complete coloring , pathwidth , outerplanar graph , chordal graph , graph , graph power , line graph
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 6, and Fiala 8. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 313–324, 2005