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.brak strony w książce