En la teoría de grafos , un L ( h , k ) -labelling , L ( h , k ) -Coloreado o, a veces L ( p , q ) -Coloreado es un (correcto) vértice coloración en el que cada par de vértices adyacentes tiene números de color que difieren en al menos h , y todos los nodos conectados por una ruta de 2 longitudes tienen sus colores difieren en al menos k . [1] de los parámetros, h y k se entiende que son enteros no negativos.
El problema se originó por un problema de asignación de canales en las redes de radio. El intervalo de un etiquetado L ( h , k ), ρ h, k (G) es la diferencia entre la frecuencia asignada más grande y la más pequeña. El objetivo del problema del etiquetado L ( h , k ) suele ser encontrar un etiquetado con un intervalo mínimo. [2] Para un gráfico dado, el intervalo mínimo sobre todas las funciones de etiquetado posibles es el λ h, k -número de G , denotado por λ h, k (G).
Cuando h = 1 y k = 0, es la coloración de vértice habitual (adecuada) .
Hay un número muy grande de artículos relativos a L ( h , k ) -labelling, con diferentes h y k parámetros y diferentes clases de gráficos.
En algunas variantes, el objetivo es minimizar la cantidad de colores utilizados (el orden ).
Ver también
Referencias
- ^ Chartrand, Gary ; Zhang, Ping (2009). "14. Colorantes, distancia y dominación". Teoría de grafos cromáticos . Prensa CRC. págs. 397–438.
- ^ Tiziana, Calamoneri (2006), "El problema de etiquetado L (h, k): una encuesta y bibliografía anotada", Computación. J. , 49 (5): 585–608, doi : 10.1093 / comjnl / bxl018