Extending fixed vertex-colourings to total colourings (Q1377889)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1110124
Language Label Description Also known as
default for all languages
No label defined
    English
    Extending fixed vertex-colourings to total colourings
    scientific article; zbMATH DE number 1110124

      Statements

      Extending fixed vertex-colourings to total colourings (English)
      0 references
      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
      0 references

      Identifiers