I have a problem which involves coloring the vertices of a graph with N vertices. In case it matters, the set of allowed colors $\{C\}$ is bigger than four.
However, there are constraints: Each vertex $V_i$ is associated with a weight $W_i$, and each color $C_k$ is associated with a number $H(C_k)$. it is then required that the coloring satisfy the constraint
$$ \dfrac{\sum_{i=1}^{N} W_i * H(C(V_i))}{\sum_{i=1}^{N} W_i} = H^* $$
where $C(V_i)$ is the color assigned to the ith vertex, and $H^*$ is some specified positive number. All quantities involved (weights etc) are positive, real numbers.
Now, because of this constraint, it seems unlikely that one could (in general) satisfy the rule of coloring that neighboring vertices should have different colors. My question then is: What is an optimal coloring for this graph, and what kinds of algorithms are available to solve such problems?
References would be most welcome.
Thanks.