JFiZO - Zadanie 09.109

3COL \le_p NEAR3COL

Graf ma mieć taką własność, że dla każdego wierzchołka może on sąsiadować z conajwyzej jednym wierzchołkiem o takim samym kolorze.

Wówczas można pokazać redukcję 3COL do naszego zmodyfikowanego problemu. Wygląda ona następująco: do każdego wierzchołka v w grafie oryginalnym dodajemy klikę pięcioelementową, łącząc każdy wierzchołek kliki z v (Czyli de facto zastępując pojedyncze wierzchołki sześcioelementowymi klikami).

• \Rightarrow Nowododanych sasiadow v (ktory ma kolor c_1) kolorujemy na: \{c_1, c_2, c_2, c_3, c_3\}.
• \Leftarrow Wierzcholek v o kolorze c_1 nie moze sasiadowac z wierzcholkiem ze starego grafu w o kolorze c_1, poniewaz nie mamy jak przypisac pieciu kolorow wierzcholkom z kliki.