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)

$|A(u)-A(v)|\notin T.$

Bibliografia

• Szablon:Cytuj książkę