Generalization of two results of Hilton on total-colourings of a graph
type: Item
instance of: scholarly article
title: Generalization of two results of Hilton on total-colourings of a graph
zbMATH Open document ID: 0824.05025
DOI: 10.1016/0012-365X(94)00291-P
published in: Discrete Mathematics
publication date: 1995-11-09T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 769315
zbMATH Keywords: results of Hilton
zbMATH Keywords: total colouring
zbMATH Keywords: total chromatic number
zbMATH Keywords: maximal matching
author: H. P. Yap
reviewed by: Timothy R. S. Walsh
MaRDI profile type: Publication
cites work: Complementary Graphs and Edge Chromatic Numbers
cites work: Nombre Chromatique Total Du Graphe R -Parti Complet
cites work: Total colorings of graphs of order \(2n\) having maximum degree \(2n-2\)
cites work: Total chromatic number of completer-partite graphs
cites work: The total chromatic number of regular graphs whose complement is bipartite
cites work: A total-chromatic number analogue of Plantholt's theorem
cites work: The total chromatic number of nearly complete bipartite graphs
cites work: The total chromatic number of graphs having large maximum degree
cites work: SOME UNSOLVED PROBLEMS IN GRAPH THEORY
cites work: Q3715121
cites work: Total Colourings of Graphs
cites work: Q4022830
Recommended article: The total chromatic number of nearly complete bipartite graphs
Recommended article: Q3832589
Recommended article: A total-chromatic number analogue of Plantholt's theorem
Recommended article: An upper bound for the total chromatic number
Recommended article: Q4010129
Recommended article: Q4327763
Recommended article: Q4242957
Recommended article: Total chromatic number of one kind of join graphs
Recommended article: An upper bound for the total chromatic number of dense graphs
Recommended article: Recent developments in total colouring
description: scientific article; zbMATH DE number 769315