Extending fixed vertex-colourings to total colourings

DOI10.1016/S0012-365X(97)00013-7MaRDI QIDQ1377889zbMATH OpenWikidataFDO

Authors Stephen A. Wong

Publication date 25 May 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(97)00013-7

zbMATH Keywords

total colouringvertex-colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Review text

Sánchez-Arroyo asked the following question in his doctoral thesis (Oxford University, 1991): Suppose \(\varphi\) is a (proper) vertex-colouring of a graph \(G\) using \(\Delta(G)+2\) colours. Can \(\varphi\) be extended to a total colouring of \(G\) using the same set of \(\Delta(G)+2\) colours? \textit{H. R. Hind} [Discrete Math. 125, No. 1-3, 211-218 (1994; Zbl 0796.05038)] showed that, in general, the answer to Sánchez-Arroyo's question is ``no for \(\Delta(G)\geq 6\). The present author gives the same answer for the case \(\Delta(G)= 5\). The question remains open for the case \(3\leq\Delta(G)\leq 4\). The answer is known to be ``yes if \(\Delta(G)= 2\).

Recommendations

• Recent developments in total colouring
• A bound on the total chromatic number
• scientific article; zbMATH DE number 4108788

Cites work

• An upper bound for the total chromatic number
• An upper bound for the total chromatic number of dense graphs
• Complementary Graphs and Edge Chromatic Numbers
• scientific article; zbMATH DE number 4150186 (Why is no real title available?)
• scientific article; zbMATH DE number 3654142 (Why is no real title available?)
• List-colourings of graphs
• Recent developments in total colouring
• SOME UNSOLVED PROBLEMS IN GRAPH THEORY
• The Total Chromatic Number of Graphs of High Minimum Degree

This page was built for publication: Extending fixed vertex-colourings to total colourings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377889)