Edge coloring is a concept from graph theory that involves assigning colors to the edges of a graph such that no two edges that share a common vertex (or are incident to the same vertex) have the same color. The main goal of edge coloring is to minimize the number of colors used. The minimum number of colors required to color the edges of a graph is known as the graph's **chromatic index** or **edge-chromatic number**.
Articles by others on the same topic
An edge colouring assigns a label called a colour to every edge of a graph: it is a function . Here this definition allows arbitrary assignments. Two edges sharing a vertex may receive the same colour. A proper edge colouring imposes the additional condition that such edges receive different colours. Some textbooks use "edge colouring" as shorthand for this proper version; check the convention before applying a theorem.[ref]
Line graphs and edge coloring. Line graphs and edge coloring, slide 1: arbitrary labeling versus proper edge coloring
The distinction matters in Ramsey theory. In a red-blue edge colouring of a complete graph, a triangle in a graph is monochromatic when its three edges have the same colour. These are arbitrary edge colourings: forbidding equal colours on edges sharing a vertex would forbid the very monochromatic triangles in a graph being sought. For example, assigning red to every edge of is a valid arbitrary edge colouring, although it is not a proper edge colouring. Colour labels can also stand for time slots: then proper edge colouring turns incompatible jobs into separate rounds.