The total chromatic number of regular graphs whose complement is bipartite (Q1318798)

Given a 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 \(\chi''(G)\) is the least number of colors in a total coloring of \(G\). There is an almost 30-years-old conjecture that for a simple graph \(G\) we have \(\Delta+ 1\leq \chi''(G)\leq \Delta+ 2\), where \(\Delta\) is the maximum vertex degree of \(G\). If \(\chi''(G)= \Delta+ 1\) then graph \(G\) is type 1 and if \(\chi''(G)= \Delta+ 2\) then \(G\) is type 2. Deciding the type of \(G\) is NP-complete. In the paper the authors prove the following theorem: Let \(G\) be a regular simple graph of even order \(2n\geq 6\) such that \(\overline G\) is bipartite. Then \(G\) is of type 1 if and only if: (i) \(G\neq K_{2n}\) and (ii) \(\overline G\neq K_{n,n}\) when \(n\) is even.