# Does this problem have a name? Minimum cost graph vertex coloring?

Given an undirected Graph $$G=(V,E)$$, a set of colors $$C$$ and a score function $$s:V\times C \rightarrow \mathbb{R}$$ that assigns each pair of color and vertex a score, find the graph coloring $$c:V\rightarrow C$$ (so that adjacent vertices have different colors, $$\forall \{u,v\}\in E : c(u)\neq c(v)$$) that minimizes (or maximizes) $$\sum_{v\in V} s(v,c(v))$$.

I found the terms "Weighted Graph coloring"/"Cost Vertex Coloring"/"Minimum Sum Coloring Problem" (where the score is just a function of the color but not the vertex) and "Graph Coloring at minimum cost" (where the cost is the sum of the differences in colors between adjacent vertices).

I am aware that this problem is equivalent to the bipartite graph matching problem (Hungarian Algorithm, by treating colors as one partition of the graph and vertices as the second partition) for complete graphs. I also know that this problem is NP-hard for arbitrary graphs and solvable in polynomial time for chordal graphs (similar to standard graph coloring). I just want to know whether there is any literature on this problem.

• This is not equivalent to bipartite matching, for which there are polynomial algorithms. In your proposed transformation, you have ignored the requirement that adjacent original vertices must have different colors. Commented Dec 3, 2022 at 1:24
• I think I wasn't clear enough: If $G$ is complete, you need (at least) $|V|$ colors to color it and can use every color at most once. You can construct a bipartite Graph $G'$, where one Partition is $V$ and the other one is $C$. The edges between the two partitions are annotated with $s$. A perfect matching on $G'$ is then equivalent to a coloring of $G$. And the coloring I look for is the matching produced by the Hungarian algorithm in $O(n^3)$. Commented Dec 5, 2022 at 14:51
• Using each color at most once is much stronger than a proper coloring in the original graph, for which only adjacent vertices must have different colors. Your transformation forces all vertex pairs (adjacent or not) to have different colors. Commented Dec 5, 2022 at 15:16

The naive solution is an $$O(3^n)$$-time algorithm by resorting to subset convolution in the $$(\min, +)$$-semi-ring. In that section, they show an $$O^*(2^n M)$$-time algorithm, provided that the cost function takes values in $$\{-M, \ldots, M\}$$.
Update: There is now an exponential-time $$(1+\varepsilon)$$-approximation algorithm that runs in time $$O^*(2^{n} \log M / \varepsilon)$$ or, alternatively, $$O^*(2^{3n/2} / \sqrt{\varepsilon})$$; the latter running time is independent of $$M$$ [2].