Abstract (EN)

We show how we can improve the approximation ratio for the independent set problem on a graph. We obtain thus an approximation ratio asymptotically equal to δ/2, in place of δ−1, where δ is the maximum degree of the graph.