Estudio poliedral del problema de la violacion cromatica minima en un grafo.

ESCALANTE, MARIANA SILVINA; UGARTE, MARIA ELISA; VARALDO, MARIA DEL CARMEN

Santa Fe

Congreso; LXIV Reunion Anual de Comunicaciones Cientificas de la Union Matematica Argentina; 2015

Unión Matemática Argentina

Sea G = (V;E) un grafo, y sea F un conjunto especial de aristas, quellamaremos aristas violables. Sea C un conjunto finito de colores. Decimosque c es un semi-coloreo si nodos en una arista no violable reciben distintos colores y en las aristas de F si pueden tener el mismo color. Dado un semi-coloreo c, definimos laviolacion cromatica de c como la cantidadde aristas de F cuyos extremos reciben un mismo color. Llamamos problemade violacion cromatica mnima (PVCM) al problema de encontrar un semi-coloreo c con volacion cromatica minima. Este problema es NP-hard y generaliza el problema clasico de coloreo de grafos.Este problema no ha sido estudiado anteriormente. En este trabajo abor-damos su tratamiento desde el punto de vista poliedral. Para ello presenta-mos una formulacion basada en el modelo estandar de coloracion de grafos.Definimos el poliedro de violacion cromatica de G comola capsula convexa de los puntos que satisfacen las condiciones planteadas.Comenzamos estudiando el poliedro analizando su dimension y sis-tema minimal de ecuaciones. Identificamos algunas familias de desigualdadesvalidas y condiciones bajo las cuales estas inducen facetas. Estas familiasestan asociadas a estructuras particulares presentes en el grafo. Por ejemplo,las semi-cliques que corresponden a una clique en el grafo G con exactamenteuna arista del conjunto F. Ademas, estan presentes desigualdades que in-ducen facetas para el poliedro de coloreo clasico, como las asociadas a losciclos sin cuerdas.