zbMATH — the first resource for mathematics

Determining the total colouring number is NP-hard. (English) Zbl 0695.05023
D. Leven and Z. Galil proved that [“NP-completeness of finding the chromatic index of regular graphs”, J. Algorithms 4, 35-44 (1983; Zbl 0509.68037)] the problem of determining the chromatic index of an arbitrary r-regular graph for \(r\geq 4\) is NP-complete. The present author proves that a 4-regular graph G is 4-edge colourable if and only if another cubic bipartite graph H is 4-total colourable. Hence the problem of determining the total chromatic number of an arbitrary cubic bipartite graph is also NP-complete.
Reviewer: H.-P.Yap

05C15 Coloring of graphs and hypergraphs
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Garey, M.; Johnson, D., Computers and intractability A guide to a NP-completeness theory, (1979), Freeman San Francisco · Zbl 0411.68039
[2] Holyer, I.J., The NP-completeness of edge colourings, SIAM J. computing, 10, 718-720, (1981) · Zbl 0473.68034
[3] Leven, D.; Galil, Z., NP-completeness of finding the chromatic index of regular graphs, J. algorithms, 4, 35-44, (1983) · Zbl 0509.68037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.