NP completeness of the edge precoloring
✍
Jiří Fiala
📂
Article
📅
2003
🏛
John Wiley and Sons
🌐
English
⚖ 63 KB
👁 1 views
## Abstract 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 co