thumb Kolorowanie krawędzi grafu – rozszerzenie klasycznego kolorowania grafu na krawędzie. Jest to przyporządkowywanie krawędziom grafu liczb naturalnych symbolizujących kolory.
Definicje
Odwzorowanie (funkcję) postaci nazywamy kolorowaniem krawędzi grafu , natomiast zbiór nazywamy wtedy: zbiorem kolorów (dla tego kolorowania).
Uwaga. Czasami – w odniesieniu do funkcji rozumianej jak w powyższym określeniu – używa się także pojęcia funkcji kolorowania (ang. coloring function), aby zaakcentować w słowie, że przy okazji przywoływania gdzieś dalej kolorowania (nazywanego dla odróżnienia, właśnie po prostu: kolorowaniem) chodzi nam nie tyle o samą jakąś (zadaną pewnym napisem) funkcję przyporządkowywania kolorów, krawędziom pewnego grafu; co pewną procedurę kolorowania – pewien szczególny zamysł (sposób rozumowania) za taką procedurą, stojący.
k-kolorowaniem nazywamy kolorowanie , czyli kolorujemy przy użyciu kolorów (w zadanym pewnym grafie).