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
    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