00858582

b

00858582 Yap, H.P. Total colourings of graphs. Lecture Notes in Mathematics. 1623. Berlin: Springer-Verlag. viii, 131 p. DM 36.00; \"oS 262.80; sFr 36.00 (1996). 1996 Berlin: Springer-Verlag EN total coloring vertex colorings edge colorings total coloring conjecture total chromatic number textbook

doi:10.1007/BFb0092895

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 {\it 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. A.T.White (Kalamazoo)