Graph coloring variation 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 &quot;defective coloring&quot;:

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)$.