DIMACS TR: 96-20
Asymptotics of the total chromatic number for simple graphs
Author: P. Mark Kayll
ABSTRACT
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