𝔖 Bobbio Scriptorium
✦   LIBER   ✦

String graphs. II. recognizing string graphs is NP-hard

✍ Scribed by Jan Kratochvíl

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
712 KB
Volume
52
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Total colouring regular bipartite graphs
Total colouring regular bipartite graphs is NP-hard
✍ Colin J.H. McDiarmid; Abdón Sánchez-Arroyo 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 437 KB

The total chromatic number of an arbitrary graph is the smallest number of colours needed to colour the edges and vertices of the graph so that no two adjacent or incident elements of the graph receive the same colour. In this paper we prove that the problem of determining the total chromatic number

Recognizing triangle-free graphs with in
Recognizing triangle-free graphs with induced path-cycle double covers is NP-complete
✍ Jacobson, Michael S.; K�zdy, Andr� E.; Lehel, Jen? 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 250 KB 👁 2 views

An induced path-cycle double cover (IPCDC) of a simple graph G is a family F Å {F 1 , . . . , F k } of induced paths and cycles of G such that if F i ʝ F j x M, then F i ʝ F j is a vertex or an edge, for i x j, each edge of G appears in precisely two of the F i 's, and each vertex of G appears in pr