Graphs of Order at Most $10$ which are Critical with Respect to the Total Chromatic Number

Abstract

A catalogue is presented which contains the graphs having order at most 10 which are critical with respect to the total chromatic number. A number of structural properties which cause these graphs to be critical are discussed, and a number of infinite classes of critical graphs are identified.A total colouring of a graph $G$ is a function assigning colours to the vertices and edges of $G$ in such a way that no two adjacent or incident elements are assigned the same colour. The total chromatic number, $\chi ”(G)$, is the minimum number of colours which need to be assigned to obtain a total colouring of the graph $G$.
A longstanding conjecture, made independently by Behzad [3] and Vizing [17], claims that
$$\mathrm{\Delta }(G)+1\le \chi ”(G)\le \mathrm{\Delta }(G)+2$$
where $\mathrm{\Delta }(G)$ is the maximum degree of $G$. The lower bound is sharp, the upper bound remains to be proved. A graph $G$ is said to be Type 1 if $\chi ”(G)=\mathrm{\Delta }(G)+1$ and is said to be Type 2 if $\chi ”(G)\ge \mathrm{\Delta }(G)+2$.

We define a graph $G$ to be critical with respect to the total chromatic number if $G$ is connected and $\chi ”(G–e)<{\chi }^{″}(G)$ for every edge $e$ in $G$. In Section 1 of this paper we identify all small order critical graphs, the catalogue of graphs is presented as a table of diagrams. In Section 2 we study structural properties of these graphs in order to identify features which cause a graph to be Type 2.