# zbMATH — the first resource for mathematics

Total colourings of graphs. (English) Zbl 0839.05001
Lecture Notes in Mathematics. 1623. Berlin: Springer-Verlag. viii, 131 p. (1996).
A total coloring of a graph combines the ideas of vertex colorings and edge colorings; now both vertices and edges are colored, and elements which are either adjacent or incident must be colored differently. Total colorings were introduced by M. Behzad [Graphs and their chromatic numbers, Doctoral Thesis, Michigan State University, 1965] and, independently, by Vizing. Both Behzad and Vizing posed what is known as the total coloring conjecture (TCC): the minimum number of colors for a total coloring of a graph $$G$$ (the total chromatic number of $$G$$) is at most two more than the maximum degree of $$G$$. It is immediate that the total chromatic number is at least one more than the maximum degree. In analogy with the situation for edge coloring, if the lower bound is attained by a graph $$G$$, then $$G$$ is said to be of Type 1; if the total chromatic number is one more than that (so that the conjectured upper bound is attained), then $$G$$ is said to be of Type 2.
The purpose of the book under review is to give an up-to-date account of studies by the author and others on total colorings, the total chromatic number, and the TCC. It is intended as a textbook for advanced undergraduate or for graduate students, and as a research reference. There are 102 references, and indices for both subject and notation. The 86 exercises include 10 marked as easy, 2 marked as hard or time consuming, and 8 open problems. The chapter titles are: (1) Basic terminology and introduction; (2) Some basic results; (3) Complete $$r$$-partite graphs; (4) Graphs of low degree; (5) Graphs of high degree; (6) Classification of Type 1 and Type 2 graphs; (7) Total chromatic number of planar graphs; (8) Some upper bounds for the total chromatic number of graphs; (9) Concluding remarks.

##### MSC:
 05-02 Research exposition (monographs, survey articles) pertaining to combinatorics 05C15 Coloring of graphs and hypergraphs 05C35 Extremal problems in graph theory 05C75 Structural characterization of families of graphs
Full Text: