Given a graph $G$, is there a 3-coloring with colors $c1$, $c2$ and $c3$ such that at most $k$ nodes are given the color $c1$ and that no two adjacent nodes are given the same color?

Is there a decently fast algorithm to solve this? My only solution is to go through every subsets of size $1$ to $k$ and remove those nodes and check if the graph is bipartite. I am also not sure if this runs in polynomial time.

  • 1
    $\begingroup$ Is $k$ a fixed constant (like 7) or part of the input? Have you tried to prove it NP-complete? $\endgroup$ – D.W. Dec 19 '20 at 6:46
  • $\begingroup$ As @D.W. says, it is polynomial time if you take $k$ to be a fixed integer, as you can solve it in $O(n^k \cdot (n+ m))$ time. Otherwise it is equivalent to 3-coloring: set $k=n$. $\endgroup$ – Pål GD Dec 19 '20 at 10:26
  • 1
    $\begingroup$ Don't edit your question to delete its content. That is considered to be vandalizing useful content. Your question exists not only for you, but also for others as well. $\endgroup$ – D.W. Dec 19 '20 at 16:58

Note that when $k$ is a fixed constant (that is, $k$ is not part of the input, for example $k = 17$ ), then the problem is easy. Indeed, in this case, your suggestion works because $n \choose l$ is polynomial in $n$, for every $l\leq k$. Also, checking whether a graph is bipartite can be done in polynomial time.

If $k$ is part of the input, then your problem is harder than the NP-complete vertex-deletion graph bipartization problem. The later problem is defined as follows. Given a graph $G$ and an integer $k\geq 0$, find a subset of at most $k$ vertices such that removing these vertices results in a bipartite graph.

To see why your problem is harder, assume that you have indeed succeeded in coloring a graph with $c_1, c_2$ and $c_3$, where at most $k$ vertices are colored with $c_1$. Then, removing the vertices that are colored with $c_1$ leaves us with a subgraph colored with $c_2$ and $c_3$, and thus the remaining subgraph has to be bipartite as two vertices with same color cannot be neighbors.

The vertex-deletion graph bipartization problem is known to be NP-complete even when restricted to planar graphs. See here.

  • $\begingroup$ I think the relation with Odd Cycle Transversal is less important than the relation with 3-coloring. $\endgroup$ – Pål GD Dec 19 '20 at 10:27

Your Answer

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