The total chromatic number of graphs having large maximum degree (Q686156)

A total-colouring \(\theta\) of a graph \(G\) is a mapping from \(V(G)\cup E(G)\) to a set \(\mathcal C\) such that no two adjacent or incident elements have the same image. The minimum cardinality of \(\mathcal C\) for which there exists a total-colouring \(\theta: V(G)\cup E(G)\to{\mathcal C}\) is called the total chromatic number of \(G\), and is denoted by \(\chi''(G)\). For simple finite graphs \(G\), it is obvious that \(\chi''(G)\geq \Delta(G)+1\), where \(\Delta(G)\) is the maximum degree of \(G\). M. Behzad and V. G. Vizing conjectured in 1965 that for any finite simple graph \(G\), \(\chi''(G)\leq \Delta(G)+2\). This conjecture is known as the Total Colouring Conjecture (TCC). It was proven that the TCC holds for graphs of low maximum degree in the 70's. Very recently the TCC was proved for graphs \(G\) (i) having \(\Delta(G)\geq | G|-4\) by \textit{H. P. Yap}, \textit{Wang Jian-Fang} and \textit{Zhang Zhongfu} [J. Aust. Math. Soc., Ser. A 47, No. 3, 445-452 (1989; Zbl 0702.05032)]; (ii) having \(\Delta(G)\geq | G|-5\) by \textit{H. P. Yap} and \textit{K. H. Chew} [J. Aust. Math. Soc., Ser. A 53, No. 2, 219-228 (1992; Zbl 0768.05043)]; (iii) having even order and minimum degree \(\delta(G)\geq{3\over 4} | G|\) by \textit{A. G. Chetwynd}, \textit{A. J. W. Hilton} and \textit{Zhao Cheng} [J. Lond. Math. Soc., II. Ser. 44, No. 2, 193-202 (1991; Zbl 0753.05033)] and having odd order with \(\delta(G)\geq {3\over 4} | G|\) by \textit{K. H. Chew} and \textit{H. P. Yap} (unpublished). The present authors prove that the TCC holds for graphs \(G\) having \(\Delta(G)\geq{3\over 4} | G|\). This is a refinement of (iii) and it supersedes (ii) when \(| G|\geq 20\). The reviewer belives that this is the most important result obtained so far in the area of total colourings of graphs because it confirms that the TCC is true for one quarter of all graphs.