×

zbMATH — the first resource for mathematics

An upper bound for the total chromatic number of dense graphs. (English) Zbl 0767.05048
Let \(\chi''(G)\) be the total chromatic number, \(\Delta(G)\) be the maximum degree, and \(n\) the order of a graph \(G\). This paper shows that \(\chi''(G)\leq\Delta(G)+2k+1\) when \(\Delta(G)\geq n/k\), where \(k\) is a (small) positive integer.

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Graphs and their chromatic numbers. Doctoral thesis, Michigan State University (1965).
[2] Graph Theory: An Introductory Course. Springer-Verlag, New York (1979). · Zbl 0411.05032
[3] Random Graphs. Academic Press, London (1985).
[4] Personal Communication.
[5] and , manuscript.
[6] Erdös, J. Combinat. Theory B 23 pp 255– (1997)
[7] Hajnal, Soc. J. Bolyai 4 pp 601– (1970)
[8] Hind, Graphs Combinat. 6 pp 153– (1990)
[9] and , manuscript.
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.