J Austral Math Soc Ser A 47 pp445--452, 1989.

Total Chromatic Number of Graphs of High Degree

H. P. Yap, Wang Jian-Fang and Zhang Zhongfu

Abstract

Using a new proof technique of the first author (by adding a new vertex to a graph and creating a total colouring of the old graph from an edge colouring of the new graph), we prove that the TCC (Total Colouring Conjecture) is true for any graph G of order n having maximum degree at least n - 4. These results together with some earlier results of M. Rosenfeld and N. Vijayaditya (who proved that the TCC is true for graphs having maximum degree at most 3), and A. V. Kostochka (who proved that the TCC is true for graphs having maximum degree 4) confirm that the TCC is true for graphs whose maximum degree is either very small or very big.

1980 AMS Subject Classification (1985 Revision): 05C15

Browse the article

Authors

H. P. Yap

Department of Mathematics, National University of Singapore, 10 Kent Ridge Crescent, Singapore 0511.

Wang Jian-Fang

Institute of Applied Mathematics, Academia Sinica, Beijing, The People's Republic of China.

Zhang Zhongfu

Department of Mathematics, Lanzhou Railway Institute, Lanzhou, Gansu, The People's Republic of China.