Description

Ce projet d'une durée d'un an, subventionné par le GDR-RO du CNRS, et impliquant des chercheurs du CEDRIC (Christophe Picouleau et Cédric Bentz) et des chercheurs du LAMSADE, avait pour objet l'étude de la complexité algorithmique du problème suivant : comment supprimer d'un graphe un nombre minimum d'arêtes de façon à diminuer son nombre chromatique d'une quantité donnée ?

Les résultats obtenus ont donné lieu à une publication en revue internationale, dont voici le DOI :

dx.doi.org/10.1007/s00373-013-1380-2