Uma coloração de arestas de um grafo $G = (V,E)$ com $n$ cores consiste em uma função $c : E \to 2$ tal que $c(e)\neq c(f)$ sempre que duas arestas distintas $e$ e $f$ possuírem uma extremidade em comum. O menor número de cores que podem ser utilizadas para realizar uma tal coloração é denotado por $\chi'(G)$, dito ser o número cromático de arestas de $G$.