Extending fixed vertex-colourings to total colourings (Q1377889)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Extending fixed vertex-colourings to total colourings |
scientific article |
Statements
Extending fixed vertex-colourings to total colourings (English)
0 references
25 May 1998
0 references
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\).
0 references
vertex-colouring
0 references
total colouring
0 references