Lovász's reduction of
COLORABILITY to 3-COLORABILITY

(Lecture notes written by Vašek Chvátal)

A problem and an infinite sequence of problems.

Consider the problem
COLORABILITY
Input: A graph G and a positive integer k.
Question: Is G k-colorable?
and, for each positive integer k, consider the problem
k-COLORABILITY
Input: A graph G.
Question: Is G k-colorable?

Two observations.

Trivially, for each positive integer k,
k-COLORABILITY reduces to COLORABILITY.
In addition, for each positive integer k,
k-COLORABILITY reduces to (k+1)-COLORABILITY:
if G' denotes the graph arising from G by adding a new vertex and making this new vertex adjacent to all the old vertices, then G is k-colorable if and only if G' is (k+1)-colorable.

A theorem of Lovász

László Lovász (Coverings and coloring of hypergraphs, Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Math., Winnipeg, Man., 1973, pp. 3--12.) proved that
COLORABILITY reduces to 3-COLORABILITY,
and so all the problems
3-COLORABILITY,
4-COLORABILITY,
5-COLORABILITY,
...
COLORABILITY
are equivalent.

A plan for the reduction

Given a graph G and a positive integer k, we are required to construct quickly a graph H such that
H is 3-colorable if and only if G is k-colorable.
The idea is to build H around a rectangular screen, an array with k rows that correspond to the colors for use in G and with n columns that correspond to the n vertices of G. To this screen, we will attach a number of peripherals whose function is to coerce every 3-coloring of H into having the following properties:
  1. only two of the three colors appear on the screen
and that these two colors can be named "green" and "red" in such a way that
  1. in each column (1,u), (2,u), ..., (k,u) of the screen,
    at least one vertex (i,u) is colored green and
  2. for each pair v,w of adjacent vertices and for each color i,
    at least one of the two vertices (i,v) and (i,w) is colored red.
If we manage to accomplish this plan, then every 3-coloring of H will point out a k-coloring f of G: specifically, f(u) is any i such that vertex (i,u) is colored green.

A peripheral to enforce property (i)

We begin the construction of H with the vertices of the screen and no edges at all; to enforce property (i), we add a new vertex b and make it adjacent to all the vertices of the screen. Since we are free to name the three colors in any 3-coloring of H whatever we want, we might as well call the color of b "blue" and to call the two other colors "green" and "red". Now property (i) is forced.

Peripherals to enforce property (ii)

There is no loss of generality in assuming that k is odd. (If k happens to be even, then we may replace k by k+1 and replace G by G' that consists of G and a new vertex adjacent to all the vertices of G: now G is k-colorable if and only if G' is (k+1)-colorable.) Under this assumption, we may enforce property (ii) by adding to H one odd cycle on k new vertices for each of the n columns of the screen, then matching the k new vertices with the k vertices of the column, and making each vertex adjacent to its mate: if all the vertices of the column were colored by the same color, then the k vertices of the odd cycle would have to be colored by the remaining two colors, which is impossible.

Peripherals to enforce property (iii)

So far "green" and "red" have been interchangeable. We will now break the symmetry by adding to H a new vertex named g and making g adjacent to b: the color of g cannot be blue and we might just as well call it green. To enforce property (iii), we add to H three vertices and six edges for each choice of i, v, and w such that i is one of the k colors for use in G and v,w are two adjacent vertices of G. The three new vertices, x, y, and z, form a triangle; the six new edges are the three edges of the triangle plus the three edges
(x,(i,v)), (y,(i,w)), (z,g).
If both (i,v) and (i,w) were colored green, then all three vertices x, y, z of the triangle would have to be colored red or blue, which is impossible.

From a k-coloring of G to a 3-coloring of H.

Now the construction of H is complete. It follows from what we have said so far that every 3-coloring of H has properties (i), (ii), (iii), and so it yields a k-coloring f of G by letting f(u) be any i such that (i,u) is colored green. Conversely, every k-coloring f of G yields a 3-coloring of H: first, each vertex (i,u) of the screen can be colored
green if f(u)=i,
red     otherwise
and then this 2-coloring of the screen can be extended into a 3-coloring of the entire H as follows. The special vertex b is colored blue and the special vertex g is colored green. As for the n odd cycles that enforce property (ii), each of them corresponds to one of the n columns of the screen; its k vertices are matched with the k vertices of the column;of these k vertices, k-1 are red and one is green. The mate of the green vertex on the cycle gets colored red; the colors on the remaining k-1 vertices of the cycle alternate between green and blue. As for the various triangles xyz that enforce property (iii), its vertex z always gets colored red; one of the vertices (i,v), (i,w) is colored red and its neighbor in the triangle gets colored green; the other one of the vertices (i,v), (i,w) is colored red or green and its neighbor in the triangle gets colored blue.

 Back to the table of contents of Vašek Chvátal's course notes