Kolo­ro­wa­nie kra­wę­dzio­we roz­róż­nia­ją­ce sąsied­nie wierz­choł­ki to kolo­ro­wa­nie wła­ści­we kra­wę­dzi, w któ­rym każ­de dwa sąsied­nie wierz­choł­ki widzą róż­ne kolo­ry incy­dent­nych do nich kra­wę­dzi. Hipo­te­za mówi, że dla gra­fów bez kra­wę­dzi izo­lo­wa­nych i o stop­niu mak­sy­mal­nym Δ rów­nym co naj­mniej 3 wystar­czy Δ+2 kolo­rów, aby otrzy­mać tego typu kolorowanie.