Edge Coloring

The assignment of colors to edges so that adjacent edges have different colors. If $m$ colors used, then referred to as $m$-edge coloring.

Edge Chromatic Number

The minimum number of colors required for proper edge coloring. Denoted by $\chi'(G)$.

For $C_n$ where $n\gt 2$:

For a complete graph $K_n$:

If $G$ is bipartite then $\chi '(G)=\Delta (G)$. $\chi'{K_{m,n}}$.

Applications

Meeting Scheduling Problem

Meeting scheduling can be modeled using edge coloring.

• vertices represent people
• edges represent meetings between pairs
• assigning a color = assigning a time slot
• adjacent edges (meetings sharing a person) cannot occur simultaneously

Explanation:

• Each person cannot attend two meetings at the same time
• Therefore, edges incident to the same vertex must have different colors

Goal:

• minimize number of colors → minimum number of time slots

Example:

• Given multiple pair meetings among students
• Find minimum time slots so no student has overlapping meetings