En teoría de grafos , una rama de las matemáticas, una coloración de radio de un grafo no dirigido es una forma de coloración de grafos en la que se asignan etiquetas enteras positivas a los grafos de modo que las etiquetas de los vértices adyacentes difieran en al menos dos, y las etiquetas de los vértices a una distancia de dos entre sí difieran en al menos uno. La coloración de radio fue estudiada por primera vez por Griggs y Yeh (1992), con un nombre diferente, etiquetado L (2,1) . [1] [2] Frank Harary lo llamó coloración de radio porque modela el problema de la asignación de canales en la radiodifusión , al tiempo que evita la interferencia electromagnética entre estaciones de radio que están cerca unas de otras tanto en el grafo como en sus frecuencias de canal asignadas.
El lapso de una coloración de radio es su etiqueta máxima, y el número de coloración de radio de un gráfico es el lapso más pequeño posible de una coloración de radio. [1] Por ejemplo, el gráfico que consta de dos vértices con un solo borde tiene el número de coloración de radio 3: tiene una coloración de radio con un vértice etiquetado como 1 y el otro etiquetado como 3, pero no es posible que una coloración de radio de este gráfico use solo las etiquetas 1 y 2.
Encontrar una coloración de radio con un lapso dado (o mínimo) es NP-completo , incluso cuando está restringido a grafos planares , grafos divididos o los complementos de grafos bipartitos . [1] [3] Sin embargo, es solucionable en tiempo polinomial para árboles y cografos . [1] [4] Para grafos arbitrarios, se puede resolver en tiempo exponencial simple , significativamente más rápido que una búsqueda de fuerza bruta a través de todas las coloraciones posibles. [5] [6]
Aunque el número de coloración de radio de un grafo de n vértices puede variar de 1 a 2 n − 1 , casi todos los grafos de n vértices tienen un número de coloración de radio exactamente n . Esto se debe a que estos grafos casi siempre tienen un diámetro de al menos dos (lo que obliga a que todos los vértices tengan colores distintos y a que el número de coloración de radio sea al menos n ), pero también casi siempre tienen un camino hamiltoniano en el grafo complementario . A los vértices consecutivos en este camino se les pueden asignar colores consecutivos, lo que permite que una coloración de radio evite omitir ningún número. [7]