page_title: Incidence coloring
section_title: Definitions
hierarchical_section_title: Incidence coloring / Definitions
caption_attribution_description: Examples of Neighborly Incidences. The * above the edge e closest to vertex v denotes incidence(v,e).
context_page_description: 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 certain constraints.
context_section_description: Below G denotes a simple graph with non-empty vertex set (non-empty) V(G), edge set E(G) and maximum degree Δ(G).
  Definition. An incidence is defined as a pair (v, e) where  is an end point of  In simple words, one says that vertex v is incident to edge e. Two incidences (v, e) and (u, f) are said to be adjacent or neighboring if one of the following holds:
  v = u, e ≠ f
  e = f, v ≠ u
  e = {v, u}, f = {u, w} and v ≠ w.
  Definition. Let I(G) be the set of all incidences of G. An incidence coloring of G is a function  that takes distinct values on adjacent incidences (we use the simplified notation c(v, u) is used instead of c((v, e)).) The minimum number of colors needed for the incidence coloring of a graph G is known as the incidence chromatic number or incidence coloring number of G, represented by  This notation was introduced by Jennifer J. Quinn Massey and Richard A. Brualdi in 1993.
caption: Examples of adjacent/neighboring incidences. The * above the edge e closest to vertex v denotes incidence (v,e).
exif: {}