Aportes al estudio del problema de coloreo de empaquetamiento en grafos.

PABLO TORRES

Valencia

Workshop; XVII Escuela Latino-Ibero Americana de Investigación Operativa; 2013

Los problemas de coloreo de grafos constituyen una familia de problemas de la Teoría de Grafos de una gran relevancia tanto teórica como práctica y se han transformado en uno de los más importantes y populares problemas combinatorios. Una de las razones es la facultad para modelizar problemas de diversas áreas.El concepto de coloreo de empaquetamiento surge al considerar problemas de asignación de frecuencias a distintas estaciones de radio, donde la distancia que debe existir entre dos estaciones de radio con la misma frecuencia para evitar interferencias depende directamente de la potencia de sus señales de transmisión.Más precisamente, un coloreo de empaquetamiento de un grafo es un coloreo del mismo tal que dos vértices pueden compartir el color $i$ si la distancia entre ellos es al menos $i + 1$. Llamamos número cromático de empaquetamiento} de un grafo $G$, y lo notamos $\chi_{\rho}(G)$, al mínimo número de colores necesarios para obtener un coloreo de empaquetamiento de $G$. Ejemplos de aplicación de este coloreo son los problemas de asignación de frecuencias en redes inalámbricas, los problemas de localización de recursos y los relativos a la  diversidad biológica donde diferentes especies en un área determinada requieren diferentes cantidades de territorio.