On hard instances of approximate vertex cover
Sundar Vishwanathan · ACM Transactions on Algorithms · 2008
We show that if there is a 2 - ϵ approximation algorithm for vertex cover on graphs with vector chromatic number at most 2 + δ, then there is a 2 - f (ϵ, δ) approximation algorithm for vertex cover for all graphs.