Results about the total chromatic number and the conformability of some families of circulant graphs (Q6094719)

A total colouring of a graph \(G=(V(G),E(G))\) is an assignment of colours to both the vertices and edges of the graph in such a way that adjacent vertices are different colours, incident edges are different colours and any vertex and edge which are incident are different colours. The total chromatic number of \(G\), \(\chi^{\prime\prime}(G)\) is the smallest possible number of colours in a total colouring. Considering a vertex of maximum degree \(\Delta\) and the \(\Delta\) edges incident with it, it is clear that \(\chi^{\prime\prime}(G)\geq \Delta(G)+1\). The total colouring conjecture is that \(\chi^{\prime\prime}(G)\leq \Delta(G)+2\): (i.e. that the naïve analogue of Vizing's theorem also works in the context of total colourings). Graphs with \(\chi^{\prime\prime}(G)=\Delta(G)+1\) are said to be Type 1 and those with \(\chi^{\prime\prime}(G)\geq \Delta(G)+2\) are Type 2. In [\textit{M. Molloy} and \textit{B. Reed}, Combinatorica 18, No. 2, 241--280 (1998; Zbl 0921.05033)], the bound \(\chi^{\prime\prime}(G)\leq \Delta(G)+10^{26}\) is shown for large enough \(\Delta(G)\) and in [\textit{C. McDiarmid} and \textit{B. Reed}, J. Comb. Theory, Ser. B 57, No. 1, 122--130 (1993; Zbl 0725.05036)] it is shown that the proportion of \(n\)-vertex graphs with \(\chi^{\prime\prime}(G)\geq \Delta(G)+2\) is \(\leq n^{-n(1+o(1))/8}\) (i.e. small) and that the proportion with \(\chi^{\prime\prime}(G)\geq \Delta(G)+3\) (if any) is \(o(c^{n^{2}})\) for some \(0\leq c<1\) (i.e. very small). In [\textit{A. G. Chetwynd} and \textit{A. J. W. Hilton}, Congr. Numerantium 66, 195--216 (1988; Zbl 0677.05026)] the concept of conformable colouring is introduced, related to total colourings, and it is shown that all Type 1 colourings are conformable. To define conformable, first let \(\text{def}(G)=\sum_{v\in V(G)}(\Delta(G)-d(v))\) where \(d(v)\) is the degree of the vertex \(v\). Of course \(\text{def}(G)\geq 0\). Now a vertex colouring with \(\Delta+1\) colours is said to be conformable if the number of colour classes (including empty colour classes, which are allowed) of parity different from that of \(\vert V(G)\vert\) is at most \(\text{def}(G)\). Though it is known that determining \(\chi^{\prime\prime}(G)\) for an arbitrary graph \(G\) is a NP-hard problem, the complexity of determining whether or not a graph has a conformable colouring is unknown. The final notion we require is that of an equitable colouring of a graph, that is one in which the cardinalities of any two colour classes differ by at most 1. In [\textit{A. Hajnal} and \textit{E. Szemerédi}, in: Combinat. Theory Appl., Colloquia Math. Soc. János Bolyai 4, 601--623 (1970; Zbl 0217.02601)], it is shown that every graph \(G\) has an equitable \(\Delta(G)+1+1\) colouring (confirming a conjecture of Erdős) and in [\textit{H. A. Kierstead} et al., Combinatorica 30, No. 2, 217--224 (2010; Zbl 1224.05176)] a polynomial-time algorithm for finding an equitable \(\Delta(G)+1\) colouring is given. The paper under review has two main purposes. The first is to explore the complexity of the conformability problem by exhibiting several families of graphs which have a \(\Delta+1\) colouring which is both conformable and equitable -- the authors suggest that this may be evidence that a polynomial-time algorithm for the conformability problem might exist. They also exhibit a conformable colouring of a family of \(2q\)-regular circulant graphs on \(2q(m+1)\) vertices for positive integers \(m\); this family contains one-fifth of 4-regular graphs. The second main aim is to investigate the total chromatic numbers of three infinite families of 4-regular circulant graphs. These turn out, with one exception which has total chromatic number \(\Delta(G)+2\), to have total chromatic number \(\Delta(G)+1\), supporting a conjecture in [\textit{R. Khennoufa} and \textit{O. Togni}, Discrete Math. 308, No. 24, 6316--6329 (2008; Zbl 1223.05074)] that in a wider family of circulants all but finitely many of the graphs are Type 1.