Discrete Methods in Informatics

October 17, 2005

Lecture 2 (edge-coloring 2)
Lecturer: Satoru Iwata

Scribe: Yasunori Horikoshi

In this course, we will cover some topics in combinatorial optimization. The textbook is [2].

1

Edge coloring of simple graph

Edge coloring of undirected graph G = (V, E) is assigning color to each edge e ∈ E so that any two edges
having end-vertex in common have different colors. The minimum number of colors required for an edge
coloring of G is denoted by γ(G).
Edge coloring is a classical problem in graph theory, especially because proving the 4-color theorem
is equivalent to showing the 3-edge-colorability of planar bridgeless cubic graphs.
For any simple graph G, the following inequality is trivial:∆(G) ≤ γ(G),where ∆(G) denotes the maximum degree among the vertices.
If G is a bipartite graph, the inequality holds with equality (Lecture 1, Thorem 1). In contrast, there
is a graph G such that ∆(G) < γ(G). Nevertheless, the next theorem has been established.
Theorem 1 (Vizing [3, 4]). For any simple graph G, we have ∆(G) ≤ γ(G) ≤ ∆(G) + 1.
We use the following lemma in the proof taken from [2, §28.1].
Lemma 2. Let G be a simple graph and let v be a vertex such that v and all its neighbours have degree
at most k, while at most one neighbour has degree precisely k. If G − v is k-edge-colorable, then so is G.
Proof. We prove this by induction on k. The case k = 0 is trivial. We may assume that precisely one
neighbour of v has degree k and the others have degree k − 1. Because we can add new vertices and edges
so that the condition holds.
Assume that G − v is k-edge-colorable. We define Xi (i = 1, 2, . . . , k) to be the set of neighbours of v
Pto which color i is not assigned. We now consider a k-edge-coloring of G − v that minimizes ki=1 |Xi |2 .
Then there is a number i (1 ≤ i ≤ k) such that |Xi | = 1. Assume otherwise, and then we have thefollowing assessment:kX|Xi | = 2deg(v) − 1 < 2k.
i=1This inequality implies that there are numbers i and j such that |Xi | = 0 and |Xj | ≥ 3. We now define
H to be the subgraph of G − v which consists of all edges colored by i or j. For any vertex s ∈ Xj , theconnected component of H containing s must be a path. We can interchange the colors of the edges along
the path, which makes |Xi |2 + |Xj |2 smaller. This contradicts to the choice of the k-edge-coloring.
Thus, we can assume Xk = {u} without loss of generality. Let G0 be the subgraph of G obtained bydeleting the edge uv and the edges of color k. Then G0 − v is (k − 1)-edge-colorable. In G0 , degrees of1

v and its neighbours are less than or equal to k − 1 and at most one neighbour has degree k − 1. So
G0 is (k − 1)-edge-colorable by the inductive assumption. Then, putting back the edges we deleted andassigning color k to the edge uv, we have k-edge-coloring of G.
Now we prove the theorem.
Proof of Theorem 1. Let k = ∆(G) + 1. Then, any vertex of G satisfies the condition of Lemma 2. Thus
we can eliminate edges from G one by one until only one edge is left. Then the resulting graph is of course
k-edge-colorable. Inductive applications of Lemma 2 accomplish the proof.
The proof gives an algorithm for finding a (∆(G) + 1)-edge-coloring in O(∆n2 ) time, where n is thenumber of vertices. Merging the vertices of degree less than ∆(G)/2, we have ∆n = O(m), where m isthe number of edges. This implies that the algorithm runs in O(nm) time.

2Coloring of complete graphWe have seen that for any simple graph G either γ(G) = ∆(G) or γ(G) = ∆(G) + 1 holds. It is known
that determining whether γ(G) = ∆(G) holds or not is NP-complete [1]. For some specific classes ofgraphs, however, we are able to determine γ(G). For example, we have the following theorem on thecomplete graphs.
Theorem 3. Let Kn be a complete graph of n vertices, then(n − 1 (n : even)γ(Kn ) =n(n : odd)
holds.
Proof. First, we show that γ(Kn ) ≤ n holds for any n. Let V = {v0 , v1 , v2 , . . . , vn−1 } be vertex set of Kn .
Then assigning color i + j (mod n) to edge vi vj gives an edge coloring.
Next, we show that γ(Kn ) > n − 1 holds for any odd n. If Kn is (n − 1)-edge-colorable then there arematchings {Mi }n−2i=0 such that Mi ∩ Mj = ∅ (i 6= j) and E = M0 ∪ M1 ∪ . . . ∪ Mn−2 . Since |Mi | ≤ (n − 1)/2,P
we have |E| = |Mi | ≤ (n − 1)2 /2, which contradicts to |E| = n(n − 1)/2 > (n − 1)2 /2.
Finally, we show that γ(Kn ) = n − 1 for any even n. The subgraph Kn − vn is (n − 1)-edgecolorable by the above method. Then the color which is not assigned to vi is 2i (mod n − 1). For eachi ∈ {0, 1, 2, . . . , n − 2} let wi := 2i (mod n − 1). Since n − 1 is odd, we have i 6= j ⇒ wi 6= wj . Thus,assigning wi to edge vi vn−1 (i = 0, 1, 2, . . . , n − 2), we obtain an (n − 1)-edge-coloring of Kn .

References[1] I. Holyer: The NP-completeness of edge-coloring, SIAM Journal on Computing 10 (1981), 718–720.
[2] A. Schrijver: Combinatorial Optimization, Springer-Verlag, 2003.
[3] V. G. Vizing: Ob otsenke khromaticheskogo klassa p-grafa [Russian; On an estimate of the chromaticclass of a p-graph], Diskretnyǐ Analiz 3 (1964), 25–30.
2[4] V. G. Vizing: Khromaticheskiǐ klass mul’tigrafa [Russian], Kibernetika 1965:3 (1965), 29–39 [Englishtranslation: The chromatic class of a multi graph, Cybernetics 1:3 (1965), 32–41].

3