Incidence (graph)

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (February 2023) (Learn how and when to remove this message)

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Incidence" graph – news · newspapers · books · scholar · JSTOR (April 2024)

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.