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

modifica

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

 

Definiamo la partizione P = {A={v1,v2,v3,v4,v5}, B={u1,u2,u3,u4} }.

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

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica