𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Determining the total colouring number is np-hard

✍ Scribed by Abdón Sánchez-Arroyo

Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
279 KB
Volume
78
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper it is proved that the problem of deteruzining the totai chromatic number of an arbitrary'graph is NP-hard. The problem remains NP-hard even for cubic bipartite graphs.

📜 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

The STO-problem is NP-hard
The STO-problem is NP-hard
✍ Krzysztof R. Apt; Peter van Emde Boas; Angelo Welling 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 209 KB

A finite set of term equations \(E\) is called subject to the occur-check (STO) if a sequence of actions of the Martelli-Montanari unification algorithm starts with \(E\) and ends with a failure due to occur-check. We prove here that the problem of deciding whether \(E\) is STO is NP-hard.

The total chromatic number of regular gr
The total chromatic number of regular graphs whose complement is bipartite
✍ J.K. Dugdale; A.J.W. Hilton 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 705 KB

We show that a regular graph G of order at least 6 whose complement c is bipartite has total chromatic number d(G) + 1 if and only if (i) G is not a complete graph, and (ii) G#K when n is even. As an aid in"';he proof of this, we also show that , for n>4, if the edges of a Hamiltonian path of Kzn a

Approximating the SVP to within a Factor
Approximating the SVP to within a Factor (1+1/dimε) Is NP-Hard under Randomized Reductions
✍ Jin-Yi Cai; Ajay Nerurkar 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 172 KB

Recently Ajtai showed that to approximate the shortest lattice vector in the l 2 -norm within a factor (1+2 &dim k ), for a sufficiently large constant k, is NP-hard under randomized reductions. We improve this result to show that to approximate a shortest lattice vector within a factor (1+dim &= ),