Problemi di colorazione

Catalogo dei problemi di ottimizzazione combinatoria · Catalogo (PDF)

• Dato un grafo non orientato \(G=(V,E)\), una soluzione assegna un colore a ogni vertice in modo che vertici adiacenti ricevano colori diversi.

• In modo equivalente, una soluzione è una partizione di \(V\) in insiemi stabili; il minimo numero di colori è il numero cromatico \(\chi(G)\).

Problema	Sigla	Differenza
Problema della colorazione dei vertici	VCP	Il problema centrale della famiglia.