La coloration des arêtes d'un graphe consiste à affecter à toutes les arêtes de ce graphe une couleur de telle sorte que deux arêtes adjacentes ne portent pas la même couleur.
L'indice chromatique du graphe G est le plus petit entier k pour lequel il existe une coloration des arêtes; on le note c(G).

Sur le graphe ci-contre, on a eu besoin de trois couleurs pour colorer les arêtes de sorte que deux arêtes adjacentes ont des couleurs différentes.

Pour colorer les arêtes d'un graphe, on peut se ramener au problème de la coloration des sommets. Il suffit pour cela de travailler non pas sur le graphe lui-même, mais sur le graphe adjoint, noté G', et que l'on définit ainsi:

• à chaque arête de G = (V, E) correspond un sommet de G' = (E, F)
• deux sommets de G' sont reliés par une arête si les deux arêtes correspondantes de G sont adjacentes.