k-Colouring Problem

computation

Definition

k-Colouring Problem

The k-colouring problem is a decision problem that asks whether the vertices of a graph can be coloured with at most $k$ colours so that no two adjacent vertices have the same colour.

Instance: graph $G$, integer $k$
Question: Does $G$ admit a proper colouring with at most $k$ colours?

For $k\ge 3$, the problem is NP-complete.

Injectivity?

A proper colouring is not globally injective, because many vertices may share the same colour. However, it is injective on every edge: if two vertices are adjacent, then they must receive different colours.

This is similar to injectivity in the sense that the colouring map never identifies elements that are forced to stay distinct.