Coloreo de empaquetamiento en ciertas familias de árboles

G. R. ARGIROFFO; G. NASINI; P. D. TORRES

Tandil

Encuentro; LX Reunión de Comunicaciones Científicas de la Unión Matemática Argentina; 2010

Numerosos problemas, como asignaciones de vuelos, asignaciones de frecuencias yproblemas de almacenamiento, pueden ser modelados como problemas de coloreo engrafos. En general, la naturaleza de cada aplicación impone restricciones adicionales,dando lugar a diferentes clases de coloreos.En particular, un k-coloreo de empaquetamiento de un grafo G es una asignaciónde los colores {1;2,ldots;k} a sus vértices de manera tal que dos nodos puedencompartir el color i si la distancia entre ellos es al menos i+1. El número rho-cromático de G, que notamos chi_ rho(G), es el mínimo k tal que G admite un k-coloreo de empaquetamiento.Si bien existen algoritmos polinomiales para calcular chi_ rho(G) en grafos split y grafos P4-tidy, el problema es NP-difícil, aún en familias particulares degrafos como los árboles. Sin embargo, se conocen subfamilias de árboles dondeel problema es polinomial. En particular, Sloper probó que es menor que 7 paraárboles de máximo grado a lo sumo 3, pero es no acotado para árboles de máximogrado a lo sumo 4.En este trabajo hallaremos nuevas familias de árboles donde el cálculo de chi_ rho(G)es polinomial.