Colorations Suboptimales

Le but de ce projet est de continuer la recherche sur les colorations suboptimales (des colorations utilisant plus de chi de G couleurs). Parmi les problèmes ouverts fingure la conjecture 2 dans [Blöchliger, de Werra. On some properties of suboptimal colorings of graphs. Networks, 43(2): 103-108, 2004], la question de l'existence des graphes planaires oligomatiques et l'optimalité de la borne donnée dans [Blöchliger, de Werra. Color-blind graphs and suboptimal colorings. Technical Report ORWP 04/04, EPFL, Switzerland, April 2004]. On cherchera également à généraliser des propriétés de colorations optimales au cas des colorations suboptimales. Selon l'avancement des recherches, on envisage d'élaborer des algorithmes en relation avec des colorations daltoniennes. Comme par exemple un algorithme exact pour colorer des généralisations du pentaK3,3 ou bien une heuristique qui trouve des colorations daltoniennes, ou plus généralement, des colorations où le nombre de couleurs différentes dans le voisinage d'un sommet soit le plus petit possible.