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$.

  • $\begingroup$ Dmitry, are you acquainted with (physical) frustration? $\endgroup$ Nov 17, 2021 at 10:37
  • $\begingroup$ @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$. $\endgroup$
    – Dmitry
    Nov 17, 2021 at 10:52
  • $\begingroup$ @RodrigodeAzevedo, the closest problem I can think of is Correlation clustering, but there is no dependence on $k$ in the objective function. $\endgroup$
    – Dmitry
    Nov 17, 2021 at 10:53
  • 1
    $\begingroup$ @Dmitry Also, for an introduction, you may want to read Brian Hayes's On the Threshold (2003) [PDF]. $\endgroup$ Nov 17, 2021 at 11:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – Juho
    Nov 17, 2021 at 11:50


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.