Uwaga. Zauważmy tutaj jednocześnie, że w powyższej definicji -kolorowania, nie oczekujemy, aby funkcja kolorowania była surjekcją, to znaczy nie żądamy wykorzystania wszystkich, czy choćby większości, z kolorów, które zostały nam dane „do dyspozycji” („przy użyciu” których, mamy kolorować). Tym samym, dla przykładu: w dowolnym grafie, za pewne -kolorowanie krawędziowe, powinniśmy także uznać sytuację, w której wszystkie krawędzie tego grafu, zostały pokolorowane tym samym (pojedynczym) kolorem.
Pewne rodzaje kolorowania krawędziowego
Prawidłowe pokolorowanie krawędzi (legalne, właściwe) to takie przyporządkowanie krawędziom kolorów, gdzie żadne dwie sąsiednie krawędzie nie są pokolorowane tak samo. (Krawędzie są sąsiednie jeśli mają wspólny jeden z końców). Czyli kolorowanie krawędzi nazywamy właściwym, jeżeli dla każdych dwóch sąsiednich krawędzi, w przeciwnym przypadku kolorowanie nazywamy niewłaściwym.
Optymalne pokolorowanie krawędzi grafu to prawidłowe (por. powyżej) pokolorowanie, przy którym zużyto najmniejszą możliwą liczbę kolorów.