Chapter 67. Edge Coloring

Vertex coloring assigns colors to vertices so that adjacent vertices receive different colors. Edge coloring assigns colors to edges so that edges sharing a common endpoint receive different colors.

This changes the nature of the problem. In vertex coloring, conflicts occur between adjacent vertices. In edge coloring, conflicts occur between incident edges.

Edge coloring models allocation problems in which edges represent tasks, connections, or interactions. Two edges that meet at a vertex cannot occur simultaneously if the shared vertex represents a limited resource.

67.1 Edge Colorings

Let $G = (V,E)$ be a graph. An edge coloring of $G$ is a function

c : E \to S,

where $S$ is a set of colors.

A coloring is proper if any two incident edges receive different colors. Thus, if edges $e$ and $f$ share a common endpoint, then

c(e) \ne c(f).

If $S = \{1,2,\ldots,k\}$ , then the coloring is called a $k$ -edge-coloring.

A graph is $k$ -edge-colorable if it admits a proper edge coloring using at most $k$ colors.

67.2 Edge Chromatic Number

The edge chromatic number of a graph $G$ , denoted by

\chi'(G),

is the least number of colors needed for a proper edge coloring.

\chi'(G) = \min\{k : G \text{ is } k\text{-edge-colorable}\}.

The notation $\chi'(G)$ distinguishes edge coloring from vertex coloring, whose chromatic number is denoted $\chi(G)$ .

The edge chromatic number is also called the chromatic index.

67.3 First Examples

Consider the path graph

P_4: \qquad v_1 - v_2 - v_3 - v_4.

This graph has three edges. The middle edge touches both remaining edges, so it must receive a different color from each. However, the two outer edges are not incident, so they may share a color.

Thus two colors suffice:

Edge	Color
$v_1v_2$	1
$v_2v_3$	2
$v_3v_4$	1

Therefore,

\chi'(P_4)=2.

Now consider the triangle $K_3$ . Every edge touches the other two edges. Therefore all three edges require distinct colors:

\chi'(K_3)=3.

Now consider the square $C_4$ . Opposite edges do not meet, so two alternating colors suffice:

\chi'(C_4)=2.

These examples already suggest that parity plays an important role in edge coloring.

67.4 Matchings and Color Classes

In a proper edge coloring, all edges of the same color are pairwise nonincident. Such a set of edges is called a matching.

Therefore every color class in an edge coloring is a matching.

Conversely, if the edge set of a graph can be partitioned into matchings, then assigning one color to each matching produces a proper edge coloring.

Thus edge coloring is equivalent to partitioning the edge set into matchings.

View	Description
Coloring view	Assign colors to edges
Matching view	Partition edges into matchings

This connection is fundamental. Much of edge coloring theory is closely related to matching theory.

67.5 Lower Bounds

Let $\Delta(G)$ denote the maximum degree of $G$ .

At any vertex $v$ , all incident edges must receive distinct colors. Since $v$ has degree $d(v)$ , at least $d(v)$ colors are required locally.

Therefore

\chi'(G) \ge \Delta(G).

This lower bound is immediate and extremely important.

For example, in the complete graph $K_5$ ,

\Delta(K_5)=4.

Thus at least four colors are required.

The surprising fact is that only one additional color is ever needed beyond this lower bound.

67.6 Vizing’s Theorem

One of the central results of edge coloring is Vizing’s Theorem.

If $G$ is a simple graph, then

\Delta(G) \le \chi'(G) \le \Delta(G)+1.

This theorem shows that every simple graph belongs to one of two classes.

Class	Condition
Class 1	$\chi'(G)=\Delta(G)$
Class 2	$\chi'(G)=\Delta(G)+1$

Thus the edge chromatic number is determined almost completely by the maximum degree.

This is very different from vertex coloring, where the chromatic number may be arbitrarily larger than the maximum degree.

For example:

Graph	$\Delta(G)$	$\chi'(G)$
Even cycle $C_{2m}$	2	2
Odd cycle $C_{2m+1}$	2	3
$K_4$	3	3
$K_5$	4	5

Odd cycles provide the simplest Class 2 graphs.

67.7 Edge Coloring of Cycles

Cycles provide a clean illustration of parity effects.

If $n$ is even, then the cycle

C_n

may be colored by alternating two colors around the cycle.

Thus

\chi'(C_{2m})=2.

If $n$ is odd, alternating colors fails when the cycle closes. The last edge conflicts with the first edge. Therefore a third color is required:

\chi'(C_{2m+1})=3.

Hence:

\chi'(C_n) = \begin{cases} 2, & n \text{ even}, \\ 3, & n \text{ odd}. \end{cases}

Odd parity creates the obstruction.

67.8 Edge Coloring of Complete Graphs

The complete graph $K_n$ has

\Delta(K_n)=n-1.

Its edge chromatic number depends on whether $n$ is even or odd.

\chi'(K_n) = \begin{cases} n-1, & n \text{ even}, \\ n, & n \text{ odd}. \end{cases}

Thus:

Graph	Edge chromatic number
$K_4$	3
$K_5$	5
$K_6$	5
$K_7$	7

When $n$ is even, the edges may be partitioned into perfect matchings. When $n$ is odd, parity prevents this.

The odd case is closely related to tournament scheduling. If $n$ teams play pairwise matches, each round corresponds to a matching. An odd number of teams forces one team to remain idle each round.

67.9 König’s Line Coloring Theorem

A major theorem for bipartite graphs is König’s Line Coloring Theorem.

If $G$ is bipartite, then

\chi'(G)=\Delta(G).

Thus every bipartite graph is Class 1.

This theorem is important both theoretically and algorithmically. Bipartite structure eliminates the parity obstructions that occur in general graphs.

For example, consider the complete bipartite graph $K_{m,n}$ . Its maximum degree is

\Delta(K_{m,n})=\max(m,n).

Therefore

\chi'(K_{m,n})=\max(m,n).

67.10 Line Graphs

Edge coloring can be converted into a vertex coloring problem.

The line graph of a graph $G$ , denoted $L(G)$ , is constructed as follows:

each edge of $G$ becomes a vertex of $L(G)$ ,
two vertices of $L(G)$ are adjacent if the corresponding edges of $G$ are incident.

Thus adjacency in the line graph represents edge incidence in the original graph.

Therefore:

\chi'(G)=\chi(L(G)).

Edge coloring becomes vertex coloring of the line graph.

This correspondence allows many edge-coloring problems to be studied through ordinary vertex coloring.

67.11 Edge Coloring and Scheduling

Edge coloring naturally models scheduling problems involving shared resources.

Suppose vertices represent processors and edges represent communication tasks. Two tasks sharing a processor cannot occur simultaneously. A proper edge coloring assigns time slots so that conflicting tasks occur at different times.

Graph concept	Scheduling meaning
Vertex	Resource
Edge	Task
Incident edges	Conflicting tasks
Color	Time slot

The edge chromatic number gives the minimum number of required time slots.

This model appears in communication networks, switch scheduling, and tournament design.

67.12 Regular Graphs

A graph is $r$ -regular if every vertex has degree $r$ .

For regular graphs, edge coloring interacts strongly with parity.

Suppose $G$ is $r$ -regular on $n$ vertices. Then

|E(G)|=\frac{rn}{2}.

If $G$ is properly edge colored using $r$ colors, then each color class must form a perfect matching. Thus each color class contains exactly $n/2$ edges.

This immediately implies that $n$ must be even.

Therefore an $r$ -regular graph on an odd number of vertices cannot be edge colored with only $r$ colors.

This explains why

\chi'(K_{2m+1})=2m+1.

67.13 Edge Coloring Algorithms

A simple greedy algorithm colors edges one at a time.

At each step, assign to the current edge the smallest available color not used on adjacent edges.

Suppose an edge $uv$ is being colored. At most

(d(u)-1)+(d(v)-1)

colors are forbidden by adjacent edges.

Since

d(u),d(v)\le \Delta(G),

at most

2\Delta(G)-2

colors are excluded.

Thus greedy coloring gives the bound

\chi'(G)\le 2\Delta(G)-1.

Vizing’s Theorem greatly improves this bound, but its proof is more subtle.

67.14 Multigraphs

In a multigraph, multiple edges may join the same pair of vertices.

Edge coloring becomes more complicated because parallel edges are mutually incident. If $m$ parallel edges connect two vertices, then all $m$ edges require different colors.

Vizing’s Theorem applies only to simple graphs. For multigraphs, stronger bounds are needed.

One classical result is Shannon’s Theorem:

\chi'(G)\le \frac{3}{2}\Delta(G)

for multigraphs.

Edge coloring of multigraphs is substantially more difficult than edge coloring of simple graphs.

67.15 Comparison with Vertex Coloring

Vertex coloring and edge coloring share similar language but behave differently.

Property	Vertex coloring	Edge coloring
Object colored	Vertices	Edges
Conflict relation	Adjacency	Incidence
Minimum number	$\chi(G)$	$\chi'(G)$
Basic lower bound	Clique number	Maximum degree
General upper bound	$\Delta+1$	$\Delta+1$
Difficulty source	Global structure	Local incidence and parity

The chromatic number of a graph may be arbitrarily large even when the maximum degree is small. Edge chromatic number behaves more rigidly because local degree structure dominates the problem.

67.16 Exercises

Find $\chi'(P_6)$ .
Find $\chi'(C_5)$ .
Prove that every matching gives a proper edge coloring with one color.
Prove that every color class in a proper edge coloring is a matching.
Find the edge chromatic number of $K_4$ .
Find the edge chromatic number of $K_6$ .
Construct the line graph of $C_4$ .
Prove that

\chi'(G)\ge \Delta(G).

Show that every bipartite graph with maximum degree 2 is edge colorable with two colors.
Give an example of a Class 2 graph.
Prove that every even cycle is 2-edge-colorable.
Prove that every odd cycle is 3-edge-colorable.
Determine the edge chromatic number of the star graph $K_{1,n}$ .
Explain why an odd regular graph cannot be decomposed into perfect matchings.
Describe a scheduling problem modeled naturally by edge coloring.