Are there variations of the classic graph coloring problem that the number of neighbors in the same color is limited but not zero (in the original problem the limit is zero)?
Problem: Given a graph $G$ and two integers $c$ and $p$, is it possible to color the vertices of $G$ with $c$ colors such that for every vertex $v$ with color $\text{color}(v)$,
$$| \{ w \in N_G(v) \mid \text{color}(v) = \text{color}(w) \} | \leq p?$$
The definition you are looking for is "defective coloring":
A $(k, d)$-coloring of a graph G is a coloring of its vertices with k colours such that each vertex v has at most d neighbours having the same colour as the vertex v. We consider k to be a positive integer (it is inconsequential to consider the case when k = 0) and d to be a non-negative integer. Hence, $(k, 0)$-coloring is equivalent to proper vertex coloring.
The minimum number of colours k required for which G is $(k, d)$-colourable is called the $d$-defective chromatic number, $\chi _{d}(G)$.
I'm not familiar with this variant, but it is still NP-complete for any fixed $p$.
Given a graph $G$ and an integer $c$, connect to each vertex $v$ a clique $C_v$ on $(p+1)c-1$ vertices.
If the original graph $G$ has a valid coloring $\chi$, then we can color the clique $C_v$ as follows: the color $\chi(v)$ appears $p$ times, and all other colors appear $p+1$ times. You can check that every vertex has exactly $p$ neighbors of the same color.
Conversely, suppose that the new graph has a coloring $\chi$ in which each vertex has at most $p$ neighbors of the same color. This is only possible if each color in $C_v$ appears at most $p+1$ times, and so some color $\chi'(v)$ appears $p$ times, and the rest appear $p+1$ times. This implies that $\chi'(v) = \chi(v)$ (since otherwise $v$ would have $p+1$ neighbors with the same colors), and furthermore that $\chi$ restricted to the original vertices is a valid coloring (in the usual sense).
