Edge colorings

Edge coloring problems often arise when objects being scheduled are pairs
of underlying elements, e.g., a pair of teams that play each other, a pair
consisting of a teacher and a class, etc. (See slides for an example.)

Definition A k-edge-coloring of a graph G is a function

f : E(G) ! {1, 2, . . . , k}. It is proper if edges that share an endpoint have
dierent colors, i.e.,
e1 \ e2 6= ; =) f (e1) 6= f (e2).
G is said to be k-edge-colorable if it has a proper k-edge-coloring.

Definition The minimum k such that G has a proper k-edge-coloring is

called the edge chromatic number of G and is denoted 0(G).

Remark Graphs with loops cannot be properly colored, so we consider

loopless graphs only.

0
Question What are easy upper and lower bounds on (G)?

0
Proposition. For any graph G, (G) (G) |E(G)|.

The above lower bound may seem trivial. However, this bound holds with
equality for large classes of graphs in particular, for bipartite graphs,
which we will prove .

Examples
For a cycle Cn, (Cn) = 2 and
(
0 2 if n even
(Cn) =
3 if n odd.

Math 104 - Prof. Kindred - Lecture 15 Page 1

 The complete graph K2n has (K2n) = 2n 1. Then we can color the
edges of K8 as illustrated below:

0
Exercise outside of class Show that (K2n+1) = 2n + 1.

Remark Note that in vertex coloring, each color class was an independent
set. In the context of edge coloring, each color class is a matching.
n
Recall that (G) (G) since color classes are independent sets for vertex
coloring. Can we obtain an analogous result for 0(G)?
0 |E(G)|
Proposition. For any graph G, (G) 0 (G) .

0
Fundamental theorem coming up =) (G) is always very close to (G)
for simple graphs G.

Theorem (Vizing). Let G be a simple graph (no loops, no multiple

edges). Then
(G) 0(G) (G) + 1.

We omit the proof of the upper bound, but you can find it in the textbook
(algorithmic proof).

Remark The simple graphs G for which 0(G) = (G) are called Class
1 graphs, and those for which 0(G) = (G)+1 are called Class 2 graphs.

The problem of deciding to which class a given graph belongs is very hard
(NP-complete).
Math 104 - Prof. Kindred - Lecture 15 Page 2
Question Does this result hold for graphs with multiple edges (loopless
graphs)?

Counterexample: fat triangle

Given 3 vtcs, say there are l edges between each pair of vtcs. (So the graph
has 3l edges total.) Then (G) = 2l and 0(G) = 3l.

The generalization of Vizings theorem for loopless graphs (or multigraphs

without loops) is the following.

Theorem. For any (loopless) graph G,

0
(G) (G) (G) + (G)
where (G) = maxuv2E(G) (u, v) and (u, v) is the # of edges with
endpoints u and v.

So (G) is the maximum of the edge multiplicities in G.

Our next goal is to show that bipartite graphs are Class 1 graphs that is,
(G)-edge-colorable. We first need a lemma.

Lemma. Every bipartite graph G has a (G)-regular bipartite super-

graph (a graph containing G).

Proof. Let G be an X, Y -bipartite graph with k = (G). A large k-regular

supergraph G0 of G can be constructed as follows.
Clone G. If G is not regular, add a vertex to X for each vertex of Y
and a vertex to Y for each vertex of X. On the new vertices, construct
another copy of G.

Math 104 - Prof. Kindred - Lecture 15 Page 3

 Add edges between vertex and its clone, as needed. For
each v 2 V (G) with dG(v) < k, join its two copies in the new graph
with k dG(v) edges to get G0.
Now G0 is a k-regular bipartite supergraph of G. (G0 is connected if G was
connected.)

See slides for an example of above construction.

Remark If G is a simple bipartite graph, then we can use a variation of the

construction above to obtain a simple (G)-regular bipartite supergraph
of G.
Replace 2nd step above with the following: For each v 2 V (G)
with dG(v) < k, join its two copies with a single edge in the new
graph to get G0.

Then
(G0) = (G) = k,
(G0) = (G) + 1,
and G0 is a supergraph of G. Iterating the 2-step process k (G)
times yields the desired simple bipartite supergraph H.

Recall Halls Marriage Thm:

Theorem. For k 2 N, every k-regular bipartite graph has a
perfect matching.

Math 104 - Prof. Kindred - Lecture 15 Page 4

 0
Theorem (Konig). If G is a bipartite graph, then (G) = (G).
Proof. Since 0(G) (G) for any graph G, it is sufficient to show that
0
(G) (G) when G is bipartite.

We give a proof by induction on (G).

Base case: Assume (G) = 1. Then no two edges share an endpoint

(since such a shared vertex would have degree at least 2), and so every edge
of G can be assigned the same color. Thus, 0(G) 1 = (G).

Induction hypothesis: Suppose any bipartite graph G with (G) = k

has 0(G) (G).

Suppose G is a bipartite graph with (G) = k + 1. By previous lemma,

there exists a (G)-regular bipartite graph H that contains G. By Halls
Marriage Thm, H has a perfect matching M . Then H M is a k-regular
bipartite graph and so by the IH, H M satisfies
0
(H M) (H M) = (H) 1 = k.

Consider any k-edge-coloring of H M . Extend it to an edge-coloring of

H by assigning all edges of M color k + 1. This is a proper (k + 1)-edge-
coloring of H since no two edges of M share an endpoint.

Since any subgraph of H must then be (k + 1)-edge-colorable, we have that

0
(G) k + 1.

Hmwk problem 7.1.21 asks you to give an algorithmic proof of Konigs

Thm. The proof yields a polynomial-time algorithm for constructing a
(G)-edge-coloring of a bipartite graph G.

Math 104 - Prof. Kindred - Lecture 15 Page 5

Line graphs

Definition Given a graph G, the line graph of G, denoted L(G), is the

graph whose vertices are the edges of G and
ef 2 E(L(G)) () e and f are edges in G with a common endpoint.
A line graph is the intersection graph of the edges of G.

Example

GG L(G)
L(G)

Observations
If e = uv is an edge in G, then dL(G)(e) = dG(u) + dG(v) 2.

The numbers of vertices and edges in L(G) are

X dG(v)
|V (L(G))| = |E(G)| and |E(L(G))| =
2
v2V (G)

The line graph of a connected graph G is connected. (Note that the

converse is not necessarily true: a disconnected graph may have a
connected line graph.)

For a simple graph G, vertices form a clique in L(G) if and only if the
corresponding edges in G have one common endpoint (a star) or form
a triangle. (Thus, !(L(G)) = (G) unless (G) = 2 and G contains
a triangle.)
Math 104 - Prof. Kindred - Lecture 15 Page 6
 The only connected graph that is isomorphic to its line graph is a cycle
graph Cn for n 3.

For a graph G, 0(G) = (L(G)). So edge coloring is really a special

case of vertex coloring.

We can characterize the graphs that exist as line graphs. A graph H is

the line graph of some other graph if and only if it is possible to find a
collection of cliques in H, partitioning the edges of H, such that each
vertex of H belongs to at most two of the cliques.

A forbidden subgraph characterization exists for line graphs, namely a

set S of nine graphs exists such that a simple graph G is a line graph
of some simple graph if and only if G does not have any graph in S as
an induced subgraph.

This characterization yields an algorithm to test whether or not G is

a line graph in polynomial time (in n = |V (G)|).

Math 104 - Prof. Kindred - Lecture 15 Page 7

Edge coloring and line graphs
Math 104, Graph Theory
March 14, 2013

Scheduling problem
Edge colorings
Edge coloring problems often arise when objects being scheduled are pairs
of underlying elements, e.g., a pair of teams that play each other, a pair
consisting of a teacher and a class, etc.

Problem
In a school, there are a teachers x1, x2, . . . , xa and b
classes y1, y2, . . . , yb. Given that teacher xi is required
to teach class yj for pij periods, schedule a complete
timetable in the minimum # of possible periods.

Define a bipartite graph with

a set X of a vtcs representing teachers,
a set Y of b vtcs representing classes
and there are pij edges between xi 2 X and yj 2 Y .
Edge-coloring a complete graph

Building a bipartite, regular supergraph

x1 x1 x1 x1
y1 y1 y1 y1
x2 x2 x2 x2
x3 y2 x3 y2 x3 y2 x3 y2
x4 x4 x4 x4
y3 y3 y3 y3
x5 x5 x5 x5

x1 x1 x1 x1
y1 y1 y1 y1
x2 x2 x2 x2
y2 x3 y2 x3 y2 x3 y2 x3
x4 x4 x4 x4
y3 y3 y3 y3
x5 x5 x5 x5
Forbidden subgraph characterization for line graphs