Graph Colouring via the Probabilistic Method

Bruce Reed

Équipe Combinatoire CNRS
Université Pierre et Marie Curie, Paris, France

Algorithms Seminar

April 21, 1997

[summary by François Morain and Philippe Robert]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

1   Introduction

Colouring a graph with the minimum number of colours is a classical problem in graph theory and has many applications. For instance, think of a cellular phone network on which each vertex (phone) must use a different frequency with its neighbours. This problem is also known to be a difficult one (see for instance [3]).

The purpose of the talk is to present a naive algorithm for colouring a certain type of graphs and explain how to analyze it with elementary probabilistic tools that we will describe first.

2   Probabilistic tools

Throughout this section we denote by Pr(A) the probability of the event A, E(X) the expected value of the random variable X, and E(X/A1,...,An) the conditional expectation of X relative to the events A1,...,An.

2.1   The Lovász Local lemma

Suppose that on some probability space W, there are n events A1,..., An that are undesirable. We wish to estimate if there is a positive probability to avoid any of them, i.e., if there is a positive lower bound for the quantity
D = Pr ( Çi=1n Aic ) ,
where Aic=W-Ai. If the events are independent, that is for any k-tuple 1£ i1<...<ik£ n,
Pr (Çj=1k A
 
ij
)=
k
Õ
j=1
Pr (A
 
ij
),
then
D=
n
Õ
1=1
(1-Pr(Ai)).
The problem is that in practice, the events are not always completely independent but weakly independent, in the sense that for each i there exists a subset ViÌ {1,...,n} such that Ai is independent of the events Aj, jÎ Vjc. In other words, Ai is possibly dependent of Aj with j in the ``neighbourhood'' Vi of i. If the cardinality of the Vi's is small, one might expect an estimate close to the one we saw for the independent case. This is the conclusion of Lovács's lemma, see [1].
Lemma 1   If the events are such that for all 1£ i£ n,
  1. Pr(Ai)£ p,
  2. Ai is independent of (Aj)jÏVi,
  3. |Vi|£ d,
and if ep(d+1)<1 then none of the events Ai, i=1,...,n, occurs with positive probability.

2.2   Azuma's inequality

If (Yi) be a sequence of independent random variables with the same distribution on {0,1}, p=Pr(Yi=1); The result of successive coin tossings is a good model for this sequence of random variables. It is well known that the time averages 1/nåi=1n Yi converges exponentially fast to p as n® +¥. Rigourously, this is Chernoff's bound
Pr æ
ç
ç
è		 ½
½
½
½
1
n
n
å
i=1
Yi-p ½
½
½
½		 >a ö
÷
÷
ø		 <2e
-a2/3np
 
,
it says basically that with high probability [p/a2] coin tossings are sufficient to get an estimate of p with an accuracy of the order of a. This kind of result has been extended, for independent variables, to the case of arbitrary distributions, i.e., not only with values in {0,1}, as long as they have an exponential moment. This is a part of large deviations theory, see [2].

Another possible generalization is to consider the case where instead of the sum of independent variables, one looks at some functional X of some arbitrary random variables Y1,...,Yn with values in {0,1}. Azuma's inequality says that if the conditional exceptions of X with respect to Y1,...,Yi do not jump sharply as i goes from 1 to n, then X is concentrated around its average value, formally,
Proposition 1   If for each i£ n,
 
max
y1,...,yi+1Î{0,1}
| E(X/Y1=y1,...,Yi=yi,Yi+1=yi+1)- E(X/Y1=y1,...,Yi=yi) | £ ci,     (1)
then
Pr ( |X-E(X)|>a ) £ 2e
-
a2
2
n
å
1
ci2
 
.
Azuma's inequality is surprisingly sharp considering the weak hypotheses of the proposition. In the independent case, for X=å1n Yi, condition (1) is satisfied with ci=1, hence the inequality is in this case,
Pr æ
ç
ç
è		 ½
½
½
½
1
n
n
å
i=1
Yi-p ½
½
½
½		 >a ö
÷
÷
ø		 <2e
-
-a2
2n
 
,
which is very close to Chernoff's bound.

3   Graph colouring

We colour a graph G such that every pair of adjacent vertices receive different colours. The chromatic number of G, noted c(G) is the minimum number of colours required to colour G. It is easy to see that, if D(G) denotes the maximal degree of G, then c(G) £ D(G)+1.

We can obtain good bounds for c(G) for certain types of graphs, as explained in [4]. For fixed e > 0, we saw that a vertex v is e-sparse if the subgraph induced by Nv, the neighbourhood of v, has at most (1-e) D(D-1)/2 edges. A graph is e-sparse if each of its vertices is e-sparse.

Theorem 1   For D sufficiently large, if G has maximum degree D and G is e-sparse, then c(G) £ (1-e/2 e6) D.

Let us indicate a rough proof of this theorem. In a first step, we construct a partial colouring C of G such for each vertex v, the number of neighbours of v which are coloured exceeds the number of colours appearing on Nv by at least e/2 e6D+1.

From this, we complete the colouring of C to a (1-e/2 e6)D-colouring of G in a greedy manner: We colour the remaining vertices one at a time. When we come to colour v, there must be an available colour: Since v has at most D neighbours (this is where the sparseness comes in), the number of colours appearing in Nv is bounded by
D - æ
ç
ç
è
e
2 e6
D+1 ö
÷
÷
ø		 .
Hence fewer than (1-e/2 e6) D colours appear in its neighbourhood.

Let us come back to the construction of C. We first assign each vertex of G a uniformly random colour from {1, 2, ..., é D/2 ù }. If two adjacent vertices have the same colour, we uncolour them. The resulting partial colouring yields C.

The first thing to show is that C is not too small, which is rather easy. Then we must study, for vertex v, the random variable Zv which counts the number of pairs of vertices in Nv which have the same colour in C. It can be shown that since G is sparse, the expectation of Zv is greater than e D / e4.

Now that we have proved that many vertices in Nv are coloured, we must show that Zv does not differ too much from its expected value. Once this is done, we use the Local Lemma to prove that every vertex will have such a property, thus proving the property on C. By a technical argument replacing Zv with a more amenable quantity, Azuma's Inequality is used to prove the assumption on Zv. Roughly speaking, the idea is that a colouring of v should not influence the colouring of the other parts of C, since G is sparse.

References

[1]
Alon (Noga) and Spencer (Joel H.). -- The probabilistic method. -- John Wiley & Sons Inc., New York, 1992, Wiley-Interscience Series in Discrete Mathematics and Optimization, xvi+254p.

[2]
Dembo (Amir) and Zeitouni (Ofer). -- Large deviations techniques and applications. -- Jones and Bartlett Publishers, Boston, MA, 1993, xiv+346p.

[3]
Karp (Richard M.). -- Reducibility among combinatorial problems. In Complexity of Computer Computations. pp. 85--103. -- New York, 1972. Proceedings of a Symposium held at IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., 1972.

[4]
Molloy (M.) and Reed (B.). -- Graph colouring via the probabilistic method. -- April 1997. Preprint.
This document was translated from LATEX by HEVEA.