En teoría de grafos , un vértice incide con una arista si el vértice es uno de los dos vértices que la arista conecta.
Una incidencia es un par donde es un vértice y es una arista incidente con
Dos incidencias distintas y son adyacentes si y sólo si , o o .
La coloración de incidencia de un gráfico es la asignación de un color a cada incidencia de G de tal forma que las incidencias adyacentes obtengan colores distintos. Es equivalente a una coloración fuerte de los bordes del gráfico obtenida al subdividir cada borde de una vez.
