Totally Coloring a Graph with Maximum Degree Four

Behzad has conjectured that a simple graph G can always be totally coloured using two more colours than the maximum degree in G. The conjecture has been verified for several special classes of graphs by Behzad, Chartrand and Cooper, Rosenfeld,
and Meyer, and by Vijayaditya for graphs with maximum degree less than or equal to 3.We show algorithmically that the conjecture is true for graphs with maximum degree 4.