Edge coloring

An assignment of colors to a graph’s edges in which any two edges sharing a vertex receive different colors. The smallest number of colors that permits such an assignment is the graph’s edge chromatic number.

Graph theory: The mathematical study of graphs, structures made of vertices connected by edges. Edge coloring is a graph-theoretic problem about assigning labels to edges.
Greedy edge coloring: An algorithmic approach that colors edges one at a time using an available color at each step. It gives a simple method for constructing a proper edge coloring.
Round-robin tournament: A competition format in which every participant plays every other participant, often arranged into rounds. Each round is a matching, so edge colors represent rounds without participant conflicts.
Vertex coloring: An assignment of colors to graph vertices so adjacent vertices receive different colors. It colors vertices rather than edges, though both problems forbid equal colors across adjacency.
Vertex degree: The number of edges incident to a vertex in a graph. Edges incident to a high-degree vertex must all receive distinct colors.
Vizing's theorem: A theorem stating that every simple graph has edge chromatic number equal to its maximum degree or one greater. It tightly bounds the number of colors needed for any simple graph.
Frequency assignment: The allocation of radio frequencies to transmitters to limit harmful interference. Edges can represent communication links that need conflict-free frequency assignments.
Total coloring: A coloring of both vertices and edges in which adjacent or incident elements receive different colors. It imposes edge-coloring constraints while also distinguishing incident vertices.
Matching: A set of edges in a graph no two of which share a vertex. Each color class in a proper edge coloring is a matching.
Kőnig's line coloring theorem: A theorem stating that every bipartite multigraph has edge chromatic number equal to its maximum degree. It gives the exact color count for bipartite graphs.

Linked from 15 pages