title: Numero cromatico dei vertici
text: # 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.
  
  