Incidence (graph)

Template:Hatnote Template:No footnotes Template:One source In graph theory, a vertex is incident with an edge if the vertex is one of the two vertices the edge connects.

An incidence is a pair $(u, e)$ where $u$ is a vertex and $e$ is an edge incident with $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 each edge of $G$ once.

References