k-colourings problem (graphs)

Statement

-colourings problem (graphs)

Given an undirected graph and integer . Does have a proper vertex colouring using -colours, if it does output the colouring and if not say so.

Solutions

Theory

• The k-colourings problem is in NP