On Total Colorings of Graphs

We show that as n → ∞ the proportion of graphs on vertices 1, 2, ..., n with total chromatic number χ″ > Δ + 1 is very small; and the proportion with χ″ > Δ + 2 is very very small. Here Δ denotes the maximum vertex degree. We also give an easy new deterministic upper bound on χ″ (proved randomly).