zbMATH — the first resource for mathematics

An improvement of Hind’s upper bound on the total chromatic number. (English) Zbl 0862.05039
In [H. R. Hind, An upper bound for the total chromatic number, Graphs Comb. 6, No. 2, 153-159 (1990; Zbl 0725.05043)] it was shown that the total chromatic number of a simple \(k\)-chromatic graph exceeds the chromatic index by at most \(2k^{1/2}\). In the paper under review, the upper bound for the difference is improved to \(18 k^{1/3} (\log (3k))^{1/2}\). The proof uses a series of lemmas about partitioning the vertices of a graph so that the degree within each part is close to its expected value; these lemmas are proved using probabilistic arguments.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Vizing, Diskret Analiz. 3 pp 25– (1964)
[2] Spencer, Ten Lectures on the Probabilistic Method (1987)
[3] Lovász, Combinatorial Problems and Exercises (1979) · Zbl 0439.05001
[4] DOI: 10.1214/aoms/1177729330 · Zbl 0048.11804 · doi:10.1214/aoms/1177729330
[5] Häggkvist, Oriented hamilton cycles in digraphs (1993)
[6] Erdös, Colloquia Mathematica Societatis János Bolyai 10. Infinite and finite sets pp 609– (1973)
[7] DOI: 10.1002/jgt.3190160206 · Zbl 0760.05036 · doi:10.1002/jgt.3190160206
[8] DOI: 10.1007/BF01787726 · Zbl 0725.05043 · doi:10.1007/BF01787726
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.