Numero cromatico dei vertici

Dato un grafo G e un insieme C di colori, il numero cromatico di G è il minimo numero di colori necessari a colorare i vertici di G in modo che, presi comunque due vertici adiacenti in G, essi abbiano diverso colore.

Per colorazione dei vertici si intende una funzione f : V(G) → C che assegna ad ogni vertice di G uno e un solo colore secondo la regola citata precedentemente.

Il numero cromatico di G si indica con la lettera greca χ(G) (chi).

Esempio

Rappresentiamo un grafo di numero cromatico 2 (grafo bipartito):

Definiamo la partizione P = {A={v₁,v₂,v₃,v₄,v₅}, B={u₁,u₂,u₃,u₄} }.

I vertici della parte A possono essere colorati dello stesso colore in quanto: per ogni x,y appartenenti ad A, con x ≠ y, l'arco {x,y} non appartiene a G; e anche per la parte B: per ogni x,y appartenenti a B, con x ≠ y, l'arco {x,y} non appartiene a G.