A kernel of order for Vertex Cover

The best known kernel for the vertex cover problem was of order 2 k for a long time, by a result of Chen et al. Recently, results by Chlebík and Clebíková, have implied that this can be improved to 2 k − 1 . In this paper, we provide a new structural result which can be used to improve this to 2 k − c , for any constant c .