Menu
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
\[
\Delta(G) + 1 \leq \chi”(G) \leq \Delta(G) + 2
\]
where \(\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) = \Delta(G) + 1\) and is said to be Type 2 if \(\chi”(G) \geq \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.