Proper vertex colouring Given a undirected graph and vertex colouring . This colouring is called proper if for all we have .