Total colourings of graphs
type: Item
instance of: scholarly article
title: Total colourings of graphs
zbMATH Open document ID: 0839.05001
published in: Lecture Notes in Mathematics
publication date: 1996-03-20T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05-02
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 858582
zbMATH Keywords: total coloring
zbMATH Keywords: vertex colorings
zbMATH Keywords: edge colorings
zbMATH Keywords: total coloring conjecture
zbMATH Keywords: total chromatic number
zbMATH Keywords: textbook
author: H. P. Yap
reviewed by: Arthur T. White
MaRDI profile type: Publication
DOI: 10.1007/BFB0092895
description: scientific article; zbMATH DE number 858582