Zamieszczamy tutaj tłumaczenie, lekko opracowane, z własnymi dowodami - pracy opracowującej następujący problem:
Dostajemy G - graf spójny. Wiemy o tym grafie, że jest przynajmniej 3-kolorowalny.
Konstruujemy graf H w ten sposób, że jego wierzchołkami są poprawne 3-kolorowania grafu G, zaś w grafie H jest krawędź pomiędzy jakimiś dwoma 3-kolorowaniami wtedy i tylko wtedy, gdy te 3-kolorowania różnią się kolorem na dokładnie jednym wierzchołku.
Dostajemy także dwa różne 3-kolorowania grafu G i naszym pytaniem jest czy pomiędzy tymi dwoma 3-kolorowaniami w grafie H istnieje ścieżka.
Ponadto w przypadku, gdy taka ścieżka istnieje rozważamy problem najkrótszej ścieżki oraz podajemy dolne ograniczenie na złożoność algorytmu szukania takiej ścieżki.
Opracował: Rafał Byczek
 |  |  |
|---|---|---|
 |  |  |
 |  |  |
 |