Introduction

We have seen that given a (c(n),d(n))-decomposition of a graph (i.e., a decomposition of the graph into clusters with diameter at most d(n) such that the cluster graph can be colored by c(n) colors), it is possible to, for example, find a maximal independent set deterministically in time c(n)d(n). The next section proves an $\Omega(\log n)$ lower bound for c(n)d(n) by giving a construction of a graph. As a part of the proof we use Sperner's lemma.