Kolorowanie kontrastowe

Kolorowanie kontrastowe ( $T$ -kolorowanie) – odmiana kolorowania wierzchołków w grafie, ma ono dwie cechy które różnią je od klasycznego kolorowania:

inne ograniczenie dotyczące kolorowania wierzchołków sąsiadujących ze sobą wierzchołków,
minimalizowaną wartością.

Klasyczne kolorowanie wierzchołków wymaga, aby sąsiadujące wierzchołki były pokolorowane różnymi kolorami. W $T$ -kolorowaniu wierzchołki sąsiadujące są kolorowane kolorami, których różnica (odległość) kolorów nie należy do pewnego zadanego zbioru $T$ (zbioru odległości zakazanych)

\left|A(u)-A(v)\right|\notin T.

Bibliografia

Marek Kubale i inni: Optymalizacja dyskretna. Modele i metody kolorowania grafów. WNT, 2002. ISBN 83-204-2747-9.