# Another version of the 3-coloring decision problem?

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.

• Is $k$ a fixed constant (like 7) or part of the input? Have you tried to prove it NP-complete? – D.W. Dec 19 '20 at 6:46
• – D.W. Dec 19 '20 at 6:46
• 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$. – Pål GD Dec 19 '20 at 10:26
• 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. – 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.