====== 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.