𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the NP-completeness of the k-colorability problem for triangle-free graphs

✍ Scribed by Frédéric Maffray; Myriam Preissmann

Book ID
108316233
Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
250 KB
Volume
162
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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