Generalization of two results of Hilton on total-colourings of a graph (Q1893175): Difference between revisions

A total colouring of a graph is a colouring of the vertices and edges such that no two adjacent vertices or edges get the same colour and no vertex gets the same colour as an edge incident to it. The total chromatic number \(\psi_ T(G)\) of a graph \(G\) is the smallest number of colours with which \(G\) can be totally coloured. In [\textit{A. J. W. Hilton}, A total-chromatic number analogue of Plantholt's theorem, Discrete Math. 79, No. 2, 169-175 (1990; Zbl 0714.05025)] it was shown that if \(G\) is graph with \(2n\) vertices and maximal vertex-degree \(\Delta(G)= 2n- 1\), and if \(\psi_ T(G)= 2n\), then \(e(\overline G)+ \alpha'(\overline G)\geq n\), where \(\overline G\) is the edge-complement of \(\overline G\), \(e(\overline G)\) is the number of edges of \(\overline G\) and \(\alpha'(\overline G)\) is the size of a maximal matching in \(\overline G\). In the article under review, it is shown that for any graph \(G\) with \(2n\) vertices, \(e(\overline G)+ \alpha'(\overline G)\geq n(2n+ 1- \psi_ T(G))\), from which the result in the aforementioned paper and several other known results are derived as special cases. In [(\(*\)) \textit{A. J. W. Hilton}, The total chromatic number of nearly complete bipartite graphs, J. Comb. Theory, Ser. B 52, No. 1, 9-19 (1991; Zbl 0743.05022)] the following result is obtained. Let \(J\) be a subgraph of the complete bipartite graph \(K_{n,n}\) and \(G\) be the graph obtained from \(K_{n,n}\) by deleting the edges of \(J\). If \(\Delta(G)= n\) and \(e(J)+ \alpha'(J)\leq n- 1\), then \(\psi_ T(G)= n+ 2\). In the article under review, it is shown that, for \(J\) and \(G\) defined as in (\(*\)), if \(\psi_ T(G)= t\) then \(e(J)+ \alpha'(J)\geq n(n+ 2- t)\), from which the result in (\(*\)) and a new one are derived.