Andrzej ŻAK

(WMS, AGH)

O grafach harmonijnych

Niech będzie dane właściwe kolorowanie krawędzi grafu pełnego $K_t$ minimalną liczbą kolorów. Wówczas tęczowym podgrafem $K_t$ nazywamy podgraf którego wszystkie krawędzie mają różne kolory.

Graf o v wierzchołkach i e krawędziach, $v \geq e$, nazywamy harmonijnym jeśli możliwe jest nadanie wierzchołkom różnych etykiet ze zbioru $\mathbb{Z}_e$ w taki sposób, aby dla każdych dwóch krawędzi sumy (mod e) etykiet na ich końcach były różne.

Przy specjalnym wyborze kolorowania grafu pełnego $K_t$ oba pojęcia okazują się blisko ze sobą powiązane.

Serdecznie zapraszamy wszystkich chętnych !