Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-19T08:28:47.170Z Has data issue: false hasContentIssue false
  • English
  • Français

An Improvement of Hind's Upper Bound on the Total Chromatic Number

Published online by Cambridge University Press:  12 September 2008

Amanda Chetwynd  and
Roland Häggkvist
Amanda Chetwynd
Affiliation:
Department of Mathematics, University of Lancaster, Lancaster LAI 4YF, UK
Roland Häggkvist
Affiliation:
Department of Mathematics, University of Umeå, S-901 87 Umeå, Sweden
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that the total chromatic number of a simple k-chromatic graph exceeds the chromatic index by at most 18k ⅓ log ½ 3k.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 5 , Issue 2 , June 1996 , pp. 99 - 104
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]H. Chernoff, H. (1952) A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals Math. Statist. 23 493–509.CrossRefGoogle Scholar
[2]Chetwynd, A. G. and Häggkvist, R. (1992) Some upper bounds on the total and list chromatic numbers of multigraphs. J. Graph Theory 16(5) 503–516.Google Scholar
[3]Erdös, P. and Lovász, L. (1973) Problems and results on 3-chromatic hypergraphs and some related questions. In Colloquia Mathematica Societatis János Bolyai 10. Infinite and finite sets, Keszthely, Hungary (Hajnal, A., Rado, R. and Sós, V. T., eds.). North-Holland, 609–627.Google Scholar
[4]Häggkvist, R. and Thomason, A. G. (1993) Oriented hamilton cycles in digraphs. Research report no. 1, Department of Mathematics, University of Umeå, Sweden.Google Scholar
[5]Hind, H. (1988) Restricted edge-colourings. Doctoral Thesis, Peterhouse College, Cambridge, UK.Google Scholar
[6]Hind, H. (1990) An upper bound for the total chromatic number. Graphs and Combinatorics 6 153–160.CrossRefGoogle Scholar
[7]Lovász, L. (1979) Combinatorial Problems and Exercises. North-Holland.Google Scholar
[8]Spencer, J. (1987) Ten Lectures on the Probabilistic Method. SIAM, Philadelphia, PA.Google Scholar
[9]Vizing, V. G. (1964) On an estimate of the chromatic class of a p-graph. Diskret Analiz. 3 25–30 (in Russian).Google Scholar