NP-completeness of a family of graph-colouring problems

AbstractIt is well known that the problem of graph k-colourability, for any k≥3, is NP-complete but that graph 2-colourability may be solved easily in polynomial time. An (s,r)-colouring of a graph G(s≥r≥1) is an assignment of r colours from a set of s to each vertex of G in such a way that no two adjacent vertices have a colour in common. The problem of (2r+1, r)-colourability for r = 1, 2, 3,… forms a family of increasingly restrictive colouring problems, the first of which is the standard 3-colourability problem. Each of these problems is shown to be NP-complete by constructing a polynomial transformation from 3-satisfiability to (2r+1, r)-colourability, valid for each value of r