2
$\begingroup$

Is the vertex cover problem remains NP-hard for 3-chromatic graphs? I am almost certain it is, but was unable to find a reference.

Thanks.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Yes, it is NP-hard via reduction to Independent Set in cubic (3-regular) graphs. Cubic graphs different from $K_4$ are 3-colorable in polynomial time via Brooks' theorem and IS remains NP-hard for them.

For a reference, check graphclasses.org.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .