Determining the total colouring number is NP-hard (Q909667): Difference between revisions

\textit{D. Leven} and \textit{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.