Incidence (graph)

An incidence graph is a Levi graph.

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 either the vertices $u,v$ or the edges $e,f$ are adjacent, which is the case if one of the following holds:

• $u=v$ and $e\neq f,$
• $e=f$ and $u\neq v,$ or
• $e=\{u,v\}$, $f=\{v,w\}$, and $u\neq w.$

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

|The Incidence Coloring Page, by Éric Sopena.