Suppose I have a connected graph $G$, where each node has degree at least $d$.
Now I want to assign two colors (blue and red) to the nodes. The constraint is that for each node, there should be $k$ ($k<d$) red nodes in his neighborhood (including himself).
I am thinking a possible way to formulate this problem:
We can use a binary variable $x_i$ to denote the color assignment to node $i$, where $x_i = 1$ means assigning red. Then for each node, we can build a linear function with integer variables: the sum of that node's neighbors (including himself) should be $k$. As a result, we can build a system of linear equations with $n$ binary variables and $n$ equations. A solution to the system of equations should be a valid color assignment.
Then I have two questions:
First, is the above formulation correct?
Second, what are the possible solutions of the system of equations (note that the variables are integers)? Is there always a solution? Can we even decide if there is a solution?