edgecoloring

Edgecoloring is the problem of assigning colors to the edges of a graph so that no two edges incident to the same vertex share a color. The smallest number of colors needed for a given graph G is called its edge chromatic number, denoted χ'(G). Let Δ denote the maximum degree of G.

A central result is Vizing's theorem (1964), which states that every simple graph has χ'(G) equal to either Δ or Δ+1. Graphs with χ'(G)=Δ are called class 1; those with χ'(G)=Δ+1 are class 2. For multigraphs, the bound can be larger, and more general bounds such as Shannon’s theorem apply.

A key special case is bipartite graphs. König’s line coloring theorem shows that for bipartite graphs χ'(G)=Δ, so an optimal edge coloring uses exactly Δ colors. This leads to efficient, constructive algorithms based on decomposing the edge set into Δ matchings.

Algorithms and complexity vary by graph class. For bipartite graphs, edge colorings with Δ colors can be found in polynomial time via maximum matching techniques and edge-disjoint decomposition. For general graphs, a Δ+1 edge-coloring can be found in polynomial time (constructive proofs of Vizing’s theorem). Determining whether χ'(G)=Δ (i.e., whether a graph is class 1) is NP-complete for general graphs with Δ≥3, making exact determination hard in the worst case.

Applications of edge coloring include scheduling problems (allocating resources over time without conflicts), frequency assignment in telecommunications, timetabling, and register allocation in compilers, where adjacent tasks or signals must use distinct resources.

Overall, edgecoloring provides a framework for assigning limited resources to overlapping constraints while avoiding conflicts.