Recent developments in total colouring
type: Item
instance of: scholarly article
title: Recent developments in total colouring
zbMATH Open document ID: 0796.05038
DOI: 10.1016/0012-365X(94)90162-7
author: V. Pereyra
published in: Discrete Mathematics
publication date: 1994-06-09T00:00:00Z
review text: A total coloring of a (finite, simple) graph is a coloring of both its edges and vertices such that no two adjacent vertices get the same color, no two adjacent edges get the same color and no incident vertex and edge get the same color. This concept was introduced in [\textit{M. Behzad}, Graphs and their chromatic number, Doctoral Thesis, Michigan State Univ. (1965)], where it was conjectured that if \(\chi'' (G)\) is the total chromatic number of the graph \(G\) (the smallest number of colors with which \(G\) can be totally colored) and \(\Delta (G)\) is its maximum degree then \(\Delta (G)+1 \leq \chi'' (G) \leq \Delta (G)+2\). In this paper, a number of recent results about total graph colorings are discussed, some examples are given to suggest that it will take recoloring schemes which are somewhat more complex than these considered up until now to prove the total coloring conjecture, and some open problems are posed.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 562665
zbMATH Keywords: total chromatic number
zbMATH Keywords: total graph colorings
zbMATH Keywords: total coloring conjecture
reviewed by: Timothy R. S. Walsh
MaRDI profile type: Publication
cites work: Complementary Graphs and Edge Chromatic Numbers
cites work: The Colour Numbers of Complete Graphs
cites work: Nombre Chromatique Total Du Graphe R -Parti Complet
cites work: Q4198785
cites work: Q4873806
cites work: A note on list-colorings
cites work: Some upper bounds on the total and list chromatic numbers of multigraphs
cites work: The Total Chromatic Number of Graphs of High Minimum Degree
cites work: The total chromatic number of graphs having large maximum degree
cites work: An upper bound for the total chromatic number
cites work: An upper bound for the total chromatic number of dense graphs
cites work: On total colourings of graphs
cites work: Determining the total colouring number is NP-hard
cites work: SOME UNSOLVED PROBLEMS IN GRAPH THEORY
description: scientific article; zbMATH DE number 562665