L(h, k)-kolorowanie
W teorii grafów oznaczanie L( h , k ) , kolorowanie L( h , k ) lub czasami kolorowanie L( p , q ) to (właściwe) kolorowanie wierzchołków , w którym każda para sąsiednich wierzchołków ma numery kolorów, które różnią się co najmniej o h , a wszystkie węzły połączone ścieżką o długości 2 mają kolory różniące się o co najmniej k . Parametry h i k są rozumiane jako nieujemne liczby całkowite.
Problem wynikał z problemu z przypisaniem kanałów w sieciach radiowych. Rozpiętość znakowania L( h , k ), ρh ,k (G) jest różnicą między największą a najmniejszą przypisaną częstotliwością. Celem problemu znakowania L( h , k ) jest zwykle znalezienie oznaczenia o minimalnej rozpiętości. Dla danego wykresu minimalną rozpiętością wszystkich możliwych funkcji etykietowania jest λ h,k -liczba G , oznaczona przez λ h,k (G).
Gdy h =1 i k =0, jest to zwykłe (właściwe) kolorowanie wierzchołków .
Istnieje bardzo duża liczba artykułów dotyczących znakowania L( h , k ), z różnymi parametrami h i k oraz różnymi klasami grafów.
W niektórych wariantach celem jest zminimalizowanie ilości użytych kolorów (kolejność ) .