::''An incidence graph is a

Levi graph In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure.. See in particulap. 181 From a collection of points and lines in an incidence geometry or a projective configuration, we form ...

.'' In

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a

vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...

is incident with an

edge Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by ...

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 Adjacent or adjacency may refer to: *Adjacent (graph theory), two vertices that are the endpoints of an edge in a graph *Adjacent (music), a conjunct step to a note which is next in the scale See also *Adjacent angles, two angles that share a c ...

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 = \

f = \{v,w\}

, and

u \neq w.

incidence coloring In graph theory, the act of coloring generally implies the assignment of labels to vertices, edges or faces in a graph. The incidence coloring is a special graph labeling where each incidence of an edge with a vertex is assigned a color under ce ...

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 Strong may refer to: Education * The Strong, an educational institution in Rochester, New York, United States * Strong Hall (Lawrence, Kansas), an administrative hall of the University of Kansas * Strong School, New Haven, Connecticut, United Sta ...

of the graph obtained by subdivising each edge of

G

once.

References

, The Incidence Coloring Page
by Éric Sopena. Graph theory objects