Colorations SuboptimalesReportar como inadecuado




Colorations Suboptimales - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Publication date: 2005

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.

Reference ROSE-STUDENT-2005-001





Autor: Bronner, Daniela

Fuente: https://infoscience.epfl.ch/record/55823?ln=en



DESCARGAR PDF




Documentos relacionados