One can consider the following generalization of the $k$-Coloring problem:

Let be given a graph $G$ and an two integers $k$ and $p$. A vertex $v$ of $G$ is properly colored if $v$ has no neighbour colored with the color of $v$. Is there a coloring of $G$ with $k$ colors such that the number of properly colored vertices in $G$ is at least $p$?

It is easy to see that for $k=3$ and $p=|V(G)|$ the problem is NP-hard, as it is equivalent to $3$-Coloring. I believe that this problem is quite a natural generalization of $k$-Coloring, though I had no success in finding it in the literature. Do you have any idea of under what name this problem might have been studied?

One can also consider the problem of maximizing the number of properly colored edges (edge is properly colored if the colors of its endpoints are distinct). This problem I have found, and it is studied under the name of Maximum $k$-Colorable Subgraph, which is equivalent to the Max $k$-Cut problem. This still does not lead me to the answer for the vertex maximization problem.

Please, if you encountered the problem before, provide some links to the literature where it has been studied. Any ideas about possible names for this problem are also appreciated. Thank you.

  • 2
    $\begingroup$ If you had an $\alpha$-approximation for this problem then by repeatedly using it you can get an $\alpha \log n$-approximation for $k$-coloring. Therefore it is not much easier than approximating $k$-coloring modulo the $\log n$ factor. $\endgroup$ – Chandra Chekuri Sep 7 '19 at 19:09

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.