Edge coloring

An edge coloring of a graph G is a function c: E(G) → C (a set of colors) such that c(e) ≠ c(f) whenever edges e and f share an endpoint. The chromatic index χ′(G) is the smallest |C| for which such a coloring exists. A graph is k-edge-colorable if χ′(G) ≤ k. Edge coloring is a special case of the general graph coloring problem, but it has its own structural theory.

For any graph, χ′(G) ≥ Δ(G), where Δ is the maximum degree, because all edges incident to a vertex must receive distinct colors. Vizing's theorem (1964) states that for simple graphs, χ′(G) ≤ Δ + 1, so the chromatic index is either Δ or Δ+1. Graphs with χ′ = Δ are called Class 1, and those with χ′ = Δ+1 are Class 2. Deciding which class a graph belongs to is NP-complete, even for cubic graphs.

Kőnig's line coloring theorem (1916) states that every bipartite graph has χ′ = Δ, meaning bipartite graphs are always Class 1. This result is constructive and leads to efficient algorithms for edge coloring bipartite graphs, which are used in scheduling problems such as assigning jobs to machines.

For regular graphs, edge coloring with Δ colors is equivalent to decomposing the edge set into Δ perfect matchings (a 1-factorization). The 1-factorization conjecture, proved by Csaba, Kühn, Lo, Osthus, and Treglown in 2016, states that every regular graph with sufficiently large degree and an even number of vertices has a 1-factorization. This was a major open problem for over 50 years.

Edge coloring models many real-world scheduling problems. In open shop scheduling, each job must be processed on each machine exactly once, and the goal is to minimize makespan; this reduces to edge coloring a bipartite multigraph, where edges represent operations and colors represent time slots. Kőnig's theorem guarantees an optimal schedule with Δ time slots.

In network design, edge coloring is used to assign wavelengths to optical connections so that no two connections sharing a fiber use the same wavelength. In register allocation for compilers, edge coloring of an interference graph (where edges represent variables that cannot share a register) is used, though this is typically vertex coloring. Edge coloring also appears in the design of round-robin tournaments and in the theory of Latin squares.

While Vizing's theorem gives a bound of Δ+1, the exact classification of Class 2 graphs is subtle. For example, the Petersen graph is Class 2, and it is the smallest bridgeless cubic graph with that property. The overfull conjecture (1986) posits that a graph with an odd number of vertices and more than Δ⌊n/2⌋ edges is Class 2, but this remains open for general graphs.

Edge coloring has connections to the four color theorem: the theorem is equivalent to the statement that every bridgeless cubic planar graph is 3-edge-colorable (Tait's reformulation). This equivalence was a driving force in the search for a proof. Additionally, the concept of list edge coloring (where each edge has a list of allowed colors) is strictly harder than ordinary edge coloring; the list chromatic index can exceed Δ+1, and the list coloring conjecture (now proved for bipartite graphs) remains open in general.

Chromatic index

The minimum number of colors needed for a proper edge coloring of a graph.

Class 1 / Class 2

Graphs with chromatic index equal to Δ are Class 1; those requiring Δ+1 are Class 2.

1-factorization

A decomposition of the edge set of a regular graph into perfect matchings.