✦ LIBER ✦

A Note on the NP-Completeness of Vertex Elimination on Directed Graphs

✍ Scribed by Gilbert, John R.

Book ID: 118212979
Publisher: Society for Industrial and Applied Mathematics
Year: 1980
Weight: 276 KB
Volume: 1
Category: Article
ISSN: 0196-5212
DOI: 10.1137/0601033

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A note on -completeness of NP-witnessing

A note on -completeness of NP-witnessing relations

✍ Noam Livne 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 129 KB

A note on approximating the min–max vert

A note on approximating the min–max vertex disjoint paths on directed acyclic graphs

✍ Bang Ye Wu 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 124 KB

Note on the reconstruction of vertex col

Note on the reconstruction of vertex colored graphs

✍ R. Taylor 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 164 KB 👁 2 views

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

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

A note on the minimum size of a vertex p

A note on the minimum size of a vertex pancyclic graph

✍ H.J. Broersma 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 152 KB