✦ LIBER ✦

On the NP-completeness of the perfect matching free subgraph problem

✍ Scribed by Mathieu Lacroix; A. Ridha Mahjoub; Sébastien Martin; Christophe Picouleau

Book ID: 113927668
Publisher: Elsevier Science
Year: 2012
Tongue: English
Weight: 231 KB
Volume: 423
Category: Article
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2011.12.065

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

NP-completeness of some generalizations

NP-completeness of some generalizations of the maximum matching problem

✍ Larry J. Stockmeyer; Vijay V. Vazirani 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 717 KB

On the NP-completeness of the k-colorabi

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

✍ Frédéric Maffray; Myriam Preissmann 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 250 KB

NP-Completeness of the linear complement

NP-Completeness of the linear complementarity problem

✍ S. J. Chung 📂 Article 📅 1989 🏛 Springer 🌐 English ⚖ 283 KB

NP-completeness of the hamming salesman

NP-completeness of the hamming salesman problem

✍ Jarmo Ernvall; Jyrki Katajainen; Martti Penttonen 📂 Article 📅 1985 🏛 Springer Netherlands 🌐 English ⚖ 211 KB

The NP-Completeness of the bandwidth min

The NP-Completeness of the bandwidth minimization problem

✍ Ch. H. Papadimitriou 📂 Article 📅 1976 🏛 Springer Vienna 🌐 English ⚖ 375 KB

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