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$.