Recent developments in total colouring (Q1322273): Difference between revisions

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.