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?