# Assign two colors to nodes in a graph with constraint

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) 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?

is the above formulation correct?

Yes.

what are the possible solutions of the system of equations... ?

They exactly correspond to the required colorings. I don’t see a different description of them.

Is there always a solution?

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.

Can we even decide if there is a solution?

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.