# Variant of Graph coloring

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?

• Re "to total coloring": I think you unintentionally 'hit' an already taken technical term: you evidently do not intend to in the end have a total coloring of your graph. Again, the meaning is clear, yet it might get even clearer if you edited your question to the mathematically precise "Given a graph $G=(V,E)$, some $S\subset V$ and a function $c\colon S\to \mathcal{C}$, my goal is to extend $c$ to [...] Sep 20, 2017 at 10:04
• a function $\overline{c}\colon V\to\mathcal{C}$ such that $\overline{c}$ is a maximizer of the number of monochromatic edges 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.) Sep 20, 2017 at 10:05
• @Peter Heining Since threshold graphs have nice structure, I expect a polynomial time algorithm to this problem. Moreover, I have not seen any hard graph problem on threshold graphs. Because of these two things I believe the problem is polytime solvable. Sep 20, 2017 at 10:21

Update 2017.09.26: As I've just learnt from Tamas Kiraly, this notion is well-studied and has several names, such as k-way cut, k-terminal cut, multiway cut. For at least three colors, the problem becomes $NP$-complete for general graphs, see E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis: The complexity of multiterminal cuts.
Earlier stuff: For two colors this can be solved in polynomial time for any graph, as it can be converted to a MinCut problem. Just connect all red vertices into a single vertex $s$, and all blue vertices into another single vertex $t$, obtaining a multigraph (or if you prefer, a graph with edge weights). The Minimum cut in this new graph between $s$ and $t$ gives the partition that gives the coloring maximizing the number of the monochromatic edges.