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

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

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

References

|The Incidence Coloring Page, by Éric Sopena.