<p>For bipartite graphs, vertex cover is polynomially solvable by routine techniques from matching theory.</p>

<p>For $k$-partite graphs with $k\ge3$, we observe the following:</p>

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

CC BY-SA 3.0
2016-03-09T18:40:37.730Z
2016-03-09T18:40:37.730Z
Gamow
<p>Given a k-partite graph which is already partitioned into k parts,
what is the complexity of finding a vertex cover of minimum size?</p>

<p>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.</p>

<graph-theory><np-hardness><complexity>
What is the complexity of vertex cover on k-partite graphs?
eleKtronaj
# What is the complexity of vertex cover on k-partite graphs?

(Asked by: username_0 on 2016-03-09)

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.

**Tags:** graph-theory, np-hardness, complexity

---

## 1 answers

### Answer by username_1 on 2016-03-09. Score: 11 | Accepted answer

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.


---

