# What is the complexity of vertex cover on k-partite graphs?

Given a k-partite graph which is already partitioned into k parts, what is the complexity of finding a vertex cover of minimum size?

I guess that it's NP-hard, but couldn't yet prove it or find reference for it. I'm also interested in the dependence on k.

For $k$-partite graphs with $k\ge3$, we observe the following:
• By Brooks' theorem, every cubic graph (except $K_4$) is 3-colorable and hence 3-partite.