Total colouring regular bipartite graphs is NP-hard (Q1313834)

Given a simple graph \(G=(V,E)\), a total coloring of \(G\) is an assignment of colors to the elements of \(V \cup E\) in such a way that no two adjacent or incident elements receive the same color. The total chromatic number is the least number of colors in a total coloring of \(G\). The authors show that the problem of deciding the total chromatic number of a \(k\)-regular bipartite graph \(G\) is NP-complete for each fixed \(k \geq 3\). This result strengthens an NP-completeness result by the second author. The polynomial reduction is from edge coloring and leads to bipartite gaphs with at least hundreds of vertices.