3
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.