En teoría de grafos , un etiquetado L( h , k ) , una coloración L( h , k ) o, a veces, una coloración L( p , q ) es una coloración de vértices (adecuada) en la que cada par de vértices adyacentes tiene números de color que difieren en al menos h , y los colores de los nodos conectados por una ruta de longitud 2 difieren en al menos k . [1] Los parámetros h y k se entienden como números enteros no negativos.
El problema se originó a partir de un problema de asignación de canal en redes de radio. El lapso 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 de etiquetado L( h , k ) es generalmente encontrar un etiquetado con un lapso mínimo. [2] Para un gráfico dado, el lapso 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, la coloración de vértice es la habitual (adecuada) .
Hay una gran cantidad de artículos sobre el etiquetado L( h , k ), con diferentes parámetros h y k y diferentes clases de gráficos.
En algunas variantes, el objetivo es minimizar el número de colores utilizados (el orden ).