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 ${\displaystyle (u,e)}$ where ${\displaystyle u}$ is a vertex and ${\displaystyle e}$ is an edge incident with ${\displaystyle u}$

Two distinct incidences ${\displaystyle (u,e)}$ and ${\displaystyle (v,f)}$ are adjacent if and only if ${\displaystyle u=v}$, ${\displaystyle e=f}$ or ${\displaystyle uv=e}$ or ${\displaystyle f}$.

An incidence coloring of a graph ${\displaystyle 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 ${\displaystyle G}$ once.

References

• |The Incidence Coloring Page, by Éric Sopena.