# Graph "coloring" problem minimal number, each edge has a colored end

(there is the possibility that the answer to my question is "Traveling Salesman, dude!". If that is the case, Please just say so and I'll try it again on my own using Traveling Salesman. We have not covered that in the lecture yet.)

again I am facing homework and thus, would appreciate it, if you did not(!) give me the solution, but helped me to get there on my own.

I've got an exercise to solve and I think, I'm pretty close, but I seem to can't get there.

I've got a graph and have to color the vertices such that the following conditions are met:

-there are two colors (a,b)

-each edge has precisely ONE a-colored vertex

-the number of a-colored vertices is minimal

I've tried to reduce the problem to 2-coloring. BUT: I don't know how to deal with the condition that the number of a-colored vertices has to be minimal. I am pretty sure that I can reduce it to a coloring problem, because I also need to show NP-completeness.

Can anyone push me into the right direction?

• Your problem is not NP-complete. It's in P. Feb 1 '16 at 16:29

A valid coloring exists iff the graph is bipartite. In that case, you can divide it into its connected components. Suppose that the $i$th connected component has $x_i$ vertices on one side, and $y_i$ on the other side. Which side would you color $a$?