Total colourings of graphs (Q1910691): Difference between revisions

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 \textit{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.