# Graph coloring problem with violations

I would like a name for the following problem. We consider a relaxed vertex coloring problem, where

• Let $$k$$ be the number of colors

• Let $$B$$ be the set of edges violating coloring, i.e., $$B := \{(u,v) \in E \mid c(u) = c(v)\}$$

• Then the objective is something like $$k + \beta |B| \to \min$$ over all colorings (for some $$\beta$$).

Does this problem have a name?

Somehow, I can't find anything. "Approximate graph coloring" and similar queries talk about approximations for graph coloring. Maybe there is another objective of form $$k^\alpha + \beta |B|^\gamma$$ (and maybe coefficients may depend on $$|V|$$)?

I am particularly interested in the hardness of such problems (the harder the better). E.g., hardness for coloring is pretty crazy. I am also particularly interested in a weighted version of this problem, e.g., $$k + \beta \sum_{e \in B} w_e \to \min$$.

• Dmitry, are you acquainted with (physical) frustration? Nov 17, 2021 at 10:37
• @RodrigodeAzevedo, I'm not familiar (I'm also almost zero in physics). I took a brief look at the article, didn't really understand it. Did I understand correctly that they only consider k=2? I need arbitrary $k$. Nov 17, 2021 at 10:52
• @RodrigodeAzevedo, the closest problem I can think of is Correlation clustering, but there is no dependence on $k$ in the objective function. Nov 17, 2021 at 10:53
• @Dmitry Also, for an introduction, you may want to read Brian Hayes's On the Threshold (2003) [PDF]. Nov 17, 2021 at 11:05
• If you want to maximize the number of properly colored edges, that's know as maximum cut. That's usually with two colors, but you can generalize.
– Juho
Nov 17, 2021 at 11:50