Numero cromatico dei vertici
# 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_1,v_2,v_3,v_4,v_5},$ $B={u_1,u_2,u_3,u_4}$ }.

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.

