edgechromatic

Edgechromatic, in the context of graph theory, refers to edge coloring: assigning colors to the edges of a graph so that no two edges sharing a common vertex have the same color. The minimum number of colors required for such a coloring is called the edge chromatic number, often denoted χ′(G). The maximum degree of the graph G is a key parameter in studying edge colorings.

A foundational result is Vizing's Theorem, which states that for any simple graph, χ′(G) is either Δ(G) or Δ(G) + 1, where Δ(G) is the maximum degree. This places the edge chromatic number within a tight bound relative to the graph’s local structure. In bipartite graphs, a stronger statement holds: χ′(G) = Δ(G). This equality extends to bipartite multigraphs as well and follows from König’s line coloring theorem.

For complete graphs, the exact value is known: χ′(K_n) = n − 1 if n is even, and χ′(K_n) = n if n is odd. This difference reflects class 1 versus class 2 graphs in edge coloring. Other small families have similarly well-characterized values; for example, a cycle C_n has χ′(C_n) = 2 when n is even and χ′(C_n) = 3 when n is odd.

Computationally, determining χ′(G) is generally hard, with exact algorithms available for specific graph classes. Edge coloring has applications in scheduling, resource allocation, and frequency assignment, where the goal is to avoid conflicts among incident tasks or channels.

See also: graph coloring, chromatic index, 1-factorization.