Edge Coloring

Graph Theory · Axiom Academy

Assigning colors to edges so that no two adjacent edges share the same color 1. Definition and Basic Example Watch as we color the edges of a simple graph. Notice that edges meeting at the same vertex must have different colors. The chromatic index (edge chromatic number) χ'(G) is the minimum number of colors needed to properly color all edges of graph G. The animation shows different graphs and their chromatic indices. For example, a complete graph K₃ (triangle) requires 3 colors, while a cycle C₄ requires only 2 colors. 3. Relation to Line Graph Vertex Coloring Edge coloring a graph G is equivalent to vertex coloring its line graph L(G) . The line graph has a vertex for each edge of G, and two vertices in L(G) are adjacent if their corresponding edges in G share a vertex. This transformation shows that χ'(G) = χ(L(G)), where χ denotes the vertex chromatic number. 4. Lower Bound: Maximum Degree A fundamental theorem in edge coloring states that the chromatic index is at least the maximum degree of the graph: This is because any vertex of degree Δ has Δ incident edges, and all these edges must receive different colors. Edge coloring has important real-world applications, particularly in scheduling problems : Time slot assignment: Assign meeting times where vertices represent people and edges represent required meetings Sports scheduling: Schedule games in a round-robin tournament Resource allocation: Assign time slots to tasks that share resources

This is the written version of the interactive lesson above. See the full Graph Theory course.