Incidence (graph)

In graph theory, an incidence is a pair ( u , e ) where u is a vertex and e is an edge incident to u .

Two distinct incidences ( u , e ) and ( v , f ) are adjacent if and only if u = v , e = f or u v = e or f .

An incidence coloring of a graph G is an assignment of a color to each incidence of G in such a way that adjacent incidences get distinct colors. It is equivalent to a strong edge coloring of the graph obtained by subdivising once each edge of G .