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

References

|The Incidence Coloring Page, by Éric Sopena.