# Coloring nodes and edges in node-weighted graph

I have a graph $$G$$ with $$n$$ nodes and $$O(n)$$ edges. Each of the nodes has a positive integral weight at least 2, such that sum of all weights is at most $$O(n)$$. We want to color the nodes and edges red or blue, where coloring a node of weight $$C$$ costs $$C$$ units, and coloring an edge costs 1 unit.

Constraints:

• Any edge between two blue nodes must be blue
• Any edge between two red nodes must be red

There are no constraints on edges between a red and a blue node.

Also given is we have exactly $$R$$ red and $$B$$ blue units of color, such that $$R + B$$ = sum of weights of nodes + edges. (Again, edges have weight 1.)

The problem is to determine whether the graph can be colored in a way that meets these constraints. Is this problem NP-complete? I suspect it is, but I am not sure which problem I can use to reduce this from.

• If the sum could be n², you could reduce from sqrt-clique by having weights n and let R be $kn+{k \choose 2}$. Nov 1, 2021 at 22:06
• This does not work though, since we could end up coloring edges even if they are not from the clique Nov 17, 2021 at 12:24