J Austral Math Soc Ser A 53 pp219--228, 1992.

Total Chromatic Number of Graphs of High Degree, II

H. P. Yap and K. J. Chew

Abstract

We prove Theorem 1: suppose G is a simple graph of order n having D(G) = n - k where k ³ 5 and n ³ max(13, 3k - 3). If G contains an independent set of k - 3 vertices, then the TCC (Total Colouring Conjecture) is true. Applying Theorem 1, we also prove that the TCC is true for any simple graph G of order n having D(G) = n - 5. The latter result together with some earlier results confirm that the TCC is true for all simple graphs whose maximaum degree is at most four and for all simple graphs of order n having maximum degree at least n - 5.

1991 AMS Subject Classification: 05C15

Browse the article

Authors

H. P. Yap

K. H. Chew

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