NP completeness of the edge precoloring extension problem on bipartite graphs

We show that the following problem is NP complete: Let G be a cubic bipartite graph and f be a precoloring of a subset of edges of G using at most three colors. Can f be extended to a proper edge 3‐coloring of the entire graph G? This result provides a natural counterpart to classical Holyer's result on edge 3‐colorability of cubic graphs and a strengthening of results on precoloring extension of perfect graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 156–160, 2003