An upper bound for the total chromatic number. (English) Zbl 0725.05043

The chromatic number, the edge chromatic number, and the total chromatic number of a graph H are respectively denoted by \(\chi\) (H), \(\chi '(H)\), and \(\chi ''(H)\). Theorem: For any graph H, \(\chi ''(H)\leq \chi '(H)+2\lceil \sqrt{\chi (H)}\rceil.\) Let \(\Delta\) (H) be the maximum degree of graph H. The proof of the theorem relies on the following interesting lemma: Let \(H=(V,E)\) be a graph with \(\chi '(H)=\Delta (H)\) and W be an independent subset of V. Any coloring of W with \(\Delta\) (H) colors can be extended to a proper coloring of \(W\cup E\) with \(\Delta (H)+1\) colors such that if edge e is colored with the new color, then one of the vertices incident with e is in W.


05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[1] Behzad, M.: Graphs and Their Chromatic Numbers. Doctoral thesis, Michigan State University 1965
[2] Behzad, M., Chartrand, G., Cooper, J.K.: The colour numbers of complete graphs. J. London Math. Soc.42, 226–228 (1967) · Zbl 0152.41203
[3] Bermond, J.-C.: Nombre chromatique total du grapher-parti complet. J. London Math. Soc. (2)9, 279–285 (1974) · Zbl 0293.05114
[4] Bollobás, B.: Graph Theory: An Introductory Course. New York: Springer-Verlag 1979 · Zbl 0688.05016
[5] Bollobás, B., Harris, A.: List-colourings of Graphs. Graphs and Combinatorics1, 115–127 (1985) · Zbl 0606.05027
[6] Kostocka, A.V.: The total coloring of a multigraph with maximal degree 4. Discrete Math.17 no. 2, 161–163 (1977) · Zbl 0411.05038
[7] Kostocka, A.V.: An analogue of Shannon’s estimate for complete colorings (Russian). Diskret. Analiz.30, 13–22 (1977)
[8] Rosenfeld, M.: On the total coloring of certain graphs. Israel J. Math9, 396–402 (1971) · Zbl 0211.56604
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.