Una arista coloración de un grafo, es una coloración de las aristas, denotada como la asignación de colores a aristas tal que aristas incidentes tengan un color distinto.