Αν G είναι ένα γράφημα και C ένα σύνολο χρωμάτων, λέμε ότι η απεικόνιση f : V → C {\displaystyle f:V\rightarrow C} είναι χρωματισμός του G όταν ∀ ∈ V, f ≠ f {\displaystyle \forall \in V,\ f\not =f} δηλαδή όταν αντιστοιχεί χρώματα στους κόμβους του G έτσι ώστε κάθε δύο συνδεμένοι κόμβοι να έχουν διαφορετικό χρώμα. Wikipedia