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?
Yes.
They exactly correspond to the required colorings. I don’t see a different description of them.
No. An example for $d=4$ and $k=1$ is the octahedron graph $O$. An example for $d=3$ and $k=2$ is a graph $O^-$ which is $O$ with one vertex removed. Indeed, since $O^-$ has a node adjacent to all other nodes of the graph, in $O^-$ should be exactly two red nodes. But then it is easy to check that there exists a node which neighborhood (including itself) contains at most one red node.
Yes, we can decide this by checking all $2^n$ possible vertex colorings of $G$. I don’t know whether is can be done faster, for instance, in polynomial time. This decicion problem may be NP-hard.