✦ LIBER ✦

Recognizing tough graphs is NP-hard

✍ Scribed by D. Bauer; S.L. Hakimi; E. Schmeichel

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 326 KB
Volume: 28
Category: Article
ISSN: 0166-218X
DOI: 10.1016/0166-218x(90)90001-s

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

String graphs. II. recognizing string gr

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

✍ Jan Kratochvíl 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 712 KB

Recognizing graphs with fixed interval n

Recognizing graphs with fixed interval number is NP-complete

✍ Douglas B. West; David B. Shmoys 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 722 KB

Recognizing string graphs in NP

✍ Marcus Schaefer; Eric Sedgwick; Daniel Štefankovič 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 219 KB

A string graph is the intersection graph of a set of curves in the plane. Each curve is represented by a vertex, and an edge between two vertices means that the corresponding curves intersect. We show that string graphs can be recognized in NP: The recognition problem was not known to be decidable u

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

On the complexity of recognizing tough g

On the complexity of recognizing tough graphs

✍ Douglas Bauer; Aurora Morgana; Edward Schmeichel 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 252 KB

The complexity of recognizing tough cubi

The complexity of recognizing tough cubic graphs

✍ D. Bauer; J. van den Heuvel; A. Morgana; E. Schmeichel 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 647 KB

We show that it is NP-hard to determine if a cubic graph G is l-tough. We then use this result to show that for any integer t > 1, it is NP-hard to determine if a 3 t-regular graph is t-tough. We conclude with some remarks concerning the complexity of recognizing certain subclasses of tough graphs.