Article contents
Total chromatic number of graphs of high degree
Published online by Cambridge University Press: 09 April 2009
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.
MSC classification
- Type
- Research Article
- Information
- Journal of the Australian Mathematical Society , Volume 47 , Issue 3 , December 1989 , pp. 445 - 452
- Copyright
- Copyright © Australian Mathematical Society 1989
References
- 11
- Cited by