𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The NP-Completeness of Edge-Coloring

✍ Scribed by Holyer, Ian

Book ID
118174079
Publisher
Society for Industrial and Applied Mathematics
Year
1981
Tongue
English
Weight
274 KB
Volume
10
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A short proof of the NP-completeness of
A short proof of the NP-completeness of minimum sum interval coloring
✍ DΓ‘niel Marx πŸ“‚ Article πŸ“… 2005 πŸ› Elsevier Science 🌐 English βš– 154 KB

In the minimum sum coloring problem we have to assign positive integers to the vertices of a graph in such a way that neighbors receive different numbers and the sum of the numbers is minimized. Szkalicki has shown that minimum sum coloring is NP-hard for interval graphs. Here we present a simpler p

NP-completeness of list coloring and pre
NP-completeness of list coloring and precoloring extension on the edges of planar graphs
✍ DΓ‘niel Marx πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 110 KB

## Abstract 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,

NP completeness of the edge precoloring
NP completeness of the edge precoloring extension problem on bipartite graphs
✍ 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