Estudio de limitaciones teóricas y aproximaciones computacionales al problema del coloreado espectral de grafos

Abstract

Dentro de los problemas de coloración de grafos, muchos existen en respuesta a una situación práctica. Para el caso de la asignación de canales en IEEE 802.11, se añade al planteamiento una matriz de distancias o "interferencias" entre los colores, lo cual da lugar al problema del espectro de umbrales, que fija el número de colores disponible y minimiza la máxima interferencia en un vértice, y a su complementario, el problema del coloreado espectral. De ambos se conocen cotas superiores generales pero amplias. En este trabajo, se han mejorado dichas cotas para algunos tipos de grafos, utilizando herramientas teóricas y computacionales para su comprobación.

In the field of graph coloring, most problems arise in response to a practical situation. For the frequency assignment problem in IEEE 802.11 (WiFi), a distance or "interference" matrix is added, which leads to the Threshold Spectrum Coloring Problem (TSC), given a fixed number of available colors, minimizes maximum interference in a vertex, and its complementary, the Chromatic Spectrum Coloring problem (CSC). General upper bounds are known for both of them. In this paper, these bounds are improved for diferent types of graphs, using theoretical and computational tools to prove them.