Edge Coloring - Definitions

Definitions

As with its vertex counterpart, an edge coloring of a graph, when mentioned without any qualification, is always assumed to be a proper coloring of the edges, meaning no two adjacent edges are assigned the same color. Here, two edges are considered to be adjacent when they share a common vertex. An edge coloring of a graph G may also be thought of as equivalent to a vertex coloring of the line graph L(G), the graph that has a vertex for every edge of G and an edge for every pair of adjacent edges in G.

A proper edge coloring with k different colors is called a (proper) k-edge-coloring. A graph that can be assigned a (proper) k-edge-coloring is said to be k-edge-colorable. The smallest number of colors needed in a (proper) edge coloring of a graph G is the chromatic index, or edge chromatic number, χ′(G). The chromatic index is also sometimes written using the notation χ₁(G); in this notation, the subscript one indicates that edges are one-dimensional objects. A graph is k-edge-chromatic if its chromatic index is exactly k. The chromatic index should not be confused with the chromatic number χ(G) or χ₀(G), the minimum number of colors needed in a proper vertex coloring of G.

Unless stated otherwise all graphs are assumed to be simple, in contrast to multigraphs in which two or more edges may connecting the same pair of endpoints and in which there may be self-loops. For many problems in edge coloring, simple graphs behave differently from multigraphs, and additional care is needed to extend theorems about edge colorings of simple graphs to the multigraph case.