chromatic number

(graph theory) The smallest number of colours needed to colour a given graph (i.e., to assign a colour to each vertex such that no two vertices connected by an edge have the same colour).