Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-27T02:31:27.740Z Has data issue: false hasContentIssue false
  • English
  • Français

Total chromatic number of graphs of high degree, II

Part of: Graph theory

Published online by Cambridge University Press:  09 April 2009

H. P. Yap  and
K. H. Chew
H. P. Yap
Affiliation:
National University of Singapore10 Kent Ridge CrescentSingapore0511
K. H. Chew
Affiliation:
National University of Singapore10 Kent Ridge CrescentSingapore0511
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We prove Theorem 1: suppose G is a simple graph of order n having Δ(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 Δ(G) = n −5. The latter result together with some earlier results confirm that the TCC is true for all simple graphs whose maximum degree is at most four and for all simple graphs of order n having maximum degree at least n − 5.

Keywords

total colouringtotal chromatic number.

MSC classification

Secondary: 05C15: Coloring of graphs and hypergraphs
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 53 , Issue 2 , October 1992 , pp. 219 - 228
Copyright
Copyright © Australian Mathematical Society 1992

References

[1]Behzad, M., Graphs and their chromatic numbers (Doctoral Thesis Michigan State Univ., 1965).Google Scholar
[2]Behzad, M., Chartrand, G. and Cooper, J. K., ‘The colour numbers of complete graphs’, J. London Math. Soc. 42 (1967), 226–228.CrossRefGoogle Scholar
[3]Chetwynd, A. G. and Hilton, A. J. W., ‘Regular graphs of high degree are 1-factorizable’, Proc. London Math. Soc. 50 (3) (1985), 193–206.CrossRefGoogle Scholar
[4]Chetwynd, A. G. and Hilton, A. J. W., ‘The chromatic index of graphs with at most four vertices of maximum degree’, in: Proc. of the Fifteenth Southeastern Conf. on Combinatorics, Graph Theory and Computing (Baton Rouge, La., 1984) Congr. Numer. 43 (1984), 221–248.Google Scholar
[5]Hilton, A. J. W., ‘Recent results on edge-colouring graphs, with applications to the totalchromatic number’, J. Combin. Math. and Combin. Computing 3 (1988), 121–134.Google Scholar
[6]Kostochka, A. V., ‘The total coloring of a multigraph with maximal degree 4’, Discrete Math. 17 (1977), 161–163.CrossRefGoogle Scholar
[7]Rosenfeld, M., ‘On the total colouring of certain graphs’, Israel J. Math. 9 (3) (1971), 396–402.CrossRefGoogle Scholar
[8]Vijayaditya, N., ‘On total chromatic number of a graph’, J. London Math. Soc. (2) 3 (1971), 405–408.CrossRefGoogle Scholar
[9]Vizing, V. G., ‘On an estimate of the chromatic class of a p-graph’, (Russian), Diskret. Analiz 3 (1964), 25–30.Google Scholar
[10]Vizing, V. G., ‘Critical graphs with a given chromatic class’ (Russian), Diskret. Analiz 5 (1965), 9–17.Google Scholar
[11]Vizing, V. G., ‘Some unsolved problems in graph theory’, Uspehi Mat. Nauk 23 (1968), 117–134 (Russian Math. Surveys 23 (1968), 125–142).Google Scholar
[12]Yap, H. P., Some topics in graph theory (Cambridge Univ. Press, 1986).CrossRefGoogle Scholar
[13]Yap, H. P., ‘Total colourings of graphs’, Bull. London Math. Soc. 21 (1989), 159–163.CrossRefGoogle Scholar
[14]Yap, H. P., Jian-Fang, Wang and Zhongfu, Zhang, ‘Total chromatic number of graphs of high degree’, J. Austral. Math. Soc. Ser. A 47 (1989), 445–452.CrossRefGoogle Scholar