What is the complexity of vertex cover on k-partite graphs?
For bipartite graphs, vertex cover is polynomially solvable by routine techniques from matching theory.

For $k$-partite graphs with $k\ge3$, we observe the following:


Vertex cover is NP-complete on cubic graphs
By Brooks' theorem, every cubic graph (except $K_4$) is 3-colorable and hence 3-partite.