Semi-total graph colourings, the beta parameter, and total chromatic number (Q2470466)

A semi-total colouring of a graph \(G\) with maximum vertex degree \(\Delta\) uses \(\Delta+1\) colors and has the properties of a total colouring except that adjacent vertices need not have distinct colours. By \(\beta(G)\) we mean the minimum number of beta edges in any semi-total colouring of \(G\). The authors prove the following: {\parindent=8mm \begin{itemize}\item[(i)]If \(\Delta= 3\) and \(G\) has a critical edge, then \(\beta(G) \leq 3\). \item[(ii)]If \(\Delta \geq 4\) and \(G\) has critical edge, then \(\beta(G) \leq \frac12 (\Delta^2- 3)\) (\(\Delta\) odd), \(\beta(G) \leq \frac12 \Delta(\Delta- 1)\) (\(\Delta\) even). \item[(iii)]If \(\Delta \geq 4\) and \(G\) has a non-triangular critical edge, then \(\beta(G) \leq (\Delta-3)\log_2(\Delta+ 1) + \frac34\Delta + 5\). \end{itemize}}