Une coloration des sommets du graphe sera dite acceptable si deux sommets adjacents n'ont pas la même couleur.
Le nombre minimum de couleurs utilisées sera appelé nombre chromatique et noté γ.
Une coloration des arcs du graphe sera dite acceptable si deux arcs adjacents n'ont pas la même couleur.
Le nombre minimum de couleurs utilisées sera appelé indice chromatique et noté q.
Nombre et Indice chromatique sont des notions duales.