Kolorowanie krawędziowe rozróżniające sąsiednie wierzchołki to kolorowanie właściwe krawędzi, w którym każde dwa sąsiednie wierzchołki widzą różne kolory incydentnych do nich krawędzi. Hipoteza mówi, że dla grafów bez krawędzi izolowanych i o stopniu maksymalnym Δ równym co najmniej 3 wystarczy Δ+2 kolorów, aby otrzymać tego typu kolorowanie.
