Incidence coloring

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

Let G = (V, E) be a simple graph with vertex set (non-empty) V(G) and edge set E(G). An incidence is defined as a pair (v, e) where v ϵ V(G) is an end point of e ϵ E(G). In simple words, one says that vertex v is incident to edge e.

Consider a set of incidences, say, I(G) = {(v,e) : v ϵ V(G) and e ϵ E(G) and v ϵ e}. The two incidences (v,e) and (u,f) are said to be adjacent if one of the given conditions holds:

An incidence coloring of G can be defined as a function c: I(G) → N such that c((v, e)) ≠ c((u,f)) for any incidences (v, e) and (u, f) that are adjacent. This implies that incidence coloring assigns distinct colors to neighborly incidences. [Generally, a simplified notation c(v, u) is used instead of c((v, e)).]

The minimum number of colors needed for incidence coloring of a graph is known as incidence chromatic number or incidence coloring number of G, represented by ${\displaystyle \chi _{i}}$(G). This notation was introduced by Jennifer J. Quinn Massey and Richard A. Brualdi in 1993.

Let A be a finite subset of N, the set of natural numbers. A is an interval if and only if it contains all the numbers between minimum of A and maximum of A. Consider c to be an incidence coloring of graph G. Let ${\displaystyle A_{c}}$(v) = {c(v,e) : v is an end point of edge e where e belongs to edge set E(G)}. An interval incidence coloring of G is an incidence coloring c of graph G such that for each vertex v in V(G), the set ${\displaystyle A_{c}}$(v) is an interval.

...
Wikipedia