This is a problem came from social network analysis.
In a vertex colored (need not be proper) graph, an edge is *monochromatic*, if both endpoints of the edge are colored with the same color. Given a partially colored network, my goal is to extend it to total coloring such that the number of *monochromatic* edges in the network is maximum.

If the network (graph) is complete graph then the problem is easy (just see which color is appearing more and assign it all uncolored vertices). Suppose if my graph is a threshold graph, then I don't have any idea how to solve it in polynomial time. Can someone help me?

monochromaticedges among all such extensions. (Note that I recommend that you replace "high" with the usual 'monochromatic'.) And is there a reason for you to expect a polynomial time algorithm for threshold graphs? (The mentioning of which currently seems surprising.) $\endgroup$ – Peter Heinig Sep 20 '17 at 10:05