DIMACS TR: 96-20

Asymptotics of the total chromatic number for simple graphs

Author: P. Mark Kayll


For simple graphs, the ratio of the total chromatic number to its linear analogue, the fractional total chromatic number, tends to one as the latter parameter grows large. Two short proofs of this fact, first observed here, are presented. One is based on a theorem of Kahn ({\em J.\ Combin.\ Theory Ser.\ A} {\bf 73} (1996), 1--59) concerning the asymptotics of the list-chromatic index, the other on recent progress of Molloy and Reed in the direction of the ``Behzad-Vizing Conjecture''. The main result has the flavour of several recent others establishing asymptotic agreement of certain integral (hyper)graph parameters with their fractional analogues.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-20.ps.gz
DIMACS Home Page