The complexity of multicolouring (Q1113919): Difference between revisions

A graph G is said to be (r,s)-colourable if each vertex of G can be assigned r colours from a given set of s colours so that adjacent vertices receive disjoint colour sets. \textit{R. W. Irving} [Discrete Appl. Math. 5, 111-117 (1983; Zbl 0504.05032)] proved that for any positive integer r, \((r,2r+1)-\)colourability is NP-complete. The present author extends Irving's result by showing that for all positive integers r and s with \(s>2r\), (r,s)-colourability is also NP-complete. The proof uses the fact that the usual \(\left( \begin{matrix} s\\ r\end{matrix} \right)\)-colouring of a graph is NP-complete.