Recent results on the total chromatic number (Q686483)

The total chromatic number \(\chi_ T(G)\) of a graph \(G\) is the least number of colours needed to colour the vertices and edges of \(G\) so that no two adjacent or incident elements receive the same colour. In 1965, M. Behzad and V. G. Vizing independently made the following conjecture (known as the Total Colouring Conjecture, abbreviated as TCC): For any simple graph \(G\), \(\Delta(G)+ 1\leq \chi_ T(G)\leq \Delta(G)+ 2\), where \(\Delta(G)\) is the maximum (vertex) degree of \(G\). Very strong evidence for the truth of the TCC has recently been provided by \textit{C. McDiarmid} and \textit{B. Reed} [J. Comb. Theory, Ser. B 57, No. 1, 122-130 (1993; Zbl 0760.05043)], who showed that the proportion of graphs of order \(n\) with \(\chi_ T(G)> \Delta(G)+ 2\) is \(o(c^{n^ 2})\) for some \(c\in (0,1)\). This paper gives a survey mainly on three types of recent results on the the total chromatic number. 1. Upper bounds for \(\chi_ T(G)\): A. G. Chetwynd, R. Häggkrist, H. Hind, C. J. H. McDiarmid, B. Reed and A. Sànchez-Arroyo have obtained several upper bounds for the total chromatic number of a graph \(G\). 2. The TCC is true for graphs of high degree: The TCC had been proved for graphs having maximum degree at most five in the 1970's. Recently, it has been proved for graphs \(G\) having \(\Delta(G)\geq | V(G)|- 5\) (the reviewer et al.) and for graphs \(G\) having \(\Delta(G)\geq {3\over 4}| V(G)|\) (the author and H. Hind). 3. The exact total chromatic number of graphs of high degree: The exact value of \(\chi_ T(G)\) for graphs \(G\) having \(\Delta(G)\geq | G|- 2\) has been determined by B. L. Chen, H. L. Fu, the author and the reviewer.