𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Total colouring regular bipartite graphs is NP-hard

✍ Scribed by Colin J.H. McDiarmid; Abdón Sánchez-Arroyo

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
437 KB
Volume
124
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 of a k-regular bipartite graph is NP-hard, for each fixed k > 3. This problem was shown to be NP-complete in [7,8]. For terminology and definitions, see [3]. Recall (roughly speaking) that NP is the class of decision *Supported by grant No. 53328 from CONACYT, MEXICO.

📜 SIMILAR VOLUMES

Determining the total colouring number i
Determining the total colouring number is np-hard
✍ Abdón Sánchez-Arroyo 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 279 KB

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.

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