摘要：Vertex colouring is a much studied problem in combinatorics and computer science for its theoretical as well as its practical aspects. In this paper we are concerned with the "distributed" version of a question stated by Vizing, concerning a Brooks-like theorem for sparse graphs. Roughly, the question asks whether there exist colourings using many fewer than Delta colours, where Delta denotes the maximum degree of the graph, provided that some sparsity conditions are satisfied. In this paper we show that such colourings not only exist, but that they can be quickly computed by extremely simple distributed, randomized algorithms. Before stating our results precisely, we review the relevant facts. For any graph G of maximum degree with n vertices, the following trivial algorithm computes a Delta+1 (list) colouring. Each vertex u initially has a list, or palette, of deg(u) + 1 colours. The computation proceeds in rounds. During each round, each uncoloured vertex, in parallel, first performs a trivial attempt: it picks a tentative colour at random from its palette and if no neighbour picks the same colour, the colour becomes final and the algorithm stops for that vertex. Otherwise, the vertex's palette undergoes a trivial update - the colours succesfully used by the neigbours are removed - and a new attempt is performed in the next round. Henceforth we shall refer to this as "the" trivial algorithm. The trivial algorithm always computes a valid colouring regardless of the composition of the initial lists, and does so in O(log n) rounds with high probability|that is, with probability approaching 1 as the number of vertices increases [10, 13, 4]. It is apparent that the trivial algorithm is distributed, since each vertex only relies on information from the neighbouring vertices. The well-known distributed algorithm for the same problem given by Luby [15] amends the trivial algorithm in the following way: at the beginning of each round every uncoloured vertex is asleep. Each such vertex awakes with probability p and executes a trivial attempt (in Luby's paper p = 1/2). Then, whether or not the vertex awoke, the palette undergoes a trivial update. At the end of the round the vertex goes back to sleep. We shall refer to this variant of the trivial algorithm as the dozing-off algorithm. The dozing-off algorithm has the same asymptotic performance as the trivial algorithm, but its analysis just needs pairwise independence. Luby used this fact to carry out a derandomization procedure in the pram model. Can better colourings|i.e. colourings using fewer colours|be computed eciently in a distributed setting? In 1948 Brooks gave a theorem that characterizes the graphs which are not {colourable: a graph is {colourable if and only if it is neither an odd cycle nor a + 1 clique (see, for instance, [2]). The proof of Brooks' theorem is actually a polynomial time sequential algorithm. {colourings can also be quickly (i.e. in polylogarithmic time) computed in the PRAM model [8, 11, 12]. In fact, a distributed version of Brooks' theorem can be derived from a certain locality property of -colourings, yielding the following: There is no o(n) randomized, synchronous protocol to -colour paths, cycles or cliques. For all other graphs, there is a randomized protocol which, with high probability, computes a -colouring in polylogarithmically many rounds [17]. (The property in question, holding for graphs which are neither cliques, paths nor cycles, is this: If G is {coloured except for one last vertex, it is possible to complete the colouring by a simple recolouring operation along an \augmenting" path of length O(log n) starting from the uncoloured vertex [17].) It is an open problem whether randomization is necessary in all of the above algorithmic results; the asymptotically best deterministic protocols known to date need O(n(n)) rounds, where (n) tends (very slowly) to zero as the number of vertices grows [1, 18]. In a 1968 paper Vizing asked whether upper bounds for the chromatic number better than those given by Brooks' Theorem existed, provided some sparsity conditions were satised. In particular, he asked what happens for triangle-free graphs. We shall refer to colourings of trianglefree graphs using signicantly fewer than colours as Brooks-Vizing colourings. This existential problem was settled about two decades later. A. Johansson [9] showed that every triangle-free graph has chromatic number O(= log). This is best-possible up to a constant factor, since Bollobas had shown the existence of graphs with arbitrarily high girth such that (G) = (=log) (the girth of a graph G is the size of the smallest cycle therein) [3]. Johansson's result, as well as an earlier result of Kim [14], which shows that graphs of girth at least 5 have chromatic number (1+o(1))= log, make use of certain distributed colouring algorithms, but their results are only existential in the following sense. They show only that the probability that the algorithm produces a valid colouring is positive. Their analyses do not rule out the possibility of their algorithms failing with a high probability. (But then, this was not their main concern.) In this paper, we show that Brooks-Vizing colourings can be computed eciently even in a distributed setting. We present very simple randomized, distributed algorithms, which are also easily implementable on a pram and in the sequential setting, and demonstrate that they produce the desired colourings with high probability. Our algorithms are variants of the dozing-o algorithm. In fact, when the input graph has no 4-cycles (girth 5 or greater) the algorithm is the dozing-o algorithm modied so that the probability that vertices awake is not constant but varies with the round. This probability, initially very low, quickly rises to one, causing the algorithm to be behave as the trivial one from that point on. For the general triangle-free (girth 4) case, the algorithm adds a mechanism which forces the vertex degrees of the uncoloured portion of the graph to remain roughly regular. This regularity is extremely useful in the analysis, but unfortunately gives the algorithm a somewhat high message and space complexity. It may be, however, that this mechanism is unnecessary. The simplicity of the algorithms is an appealing feature and we expect them to work quite well in practice. Although these algorithms display similarities to those in Kim's work [14], we have striven for speed and simplicity. Moreover, our analyses are much simpler than those given there. It is perhaps worth remarking that our analyses demonstrate that Brooks-Vizing colourings are not rare, for the randomized colour assignments computed by the algorithm almost always produces such a colouring. Furthermore, they highlight the role played by the girth assumption. Our result may be conveniently stated as follows: We give an algorithm which, for any triangle-free, D-regular input graph G such that D log1+ n, where > 0 is any xed constant, computes with probability 1−o(1) a vertex colouring of G using D=k colours, for any k logD, where is a constant which depends on . Moreover, with probability 1 − o(1), the colouring will be completed within O k + log n logD rounds in the synchronous, message-passing distributed model of computation (with no shared memory). Both of the above o(1) terms are functions going to 0 with n, the number of vertices in the network. The statement of the theorem allows some flexibility in the choice of k and D. For instance, by choosing D nc= log log n, where c > 1 is any constant, and k = log log n, the algorithm will compute a (D= log log n)- colouring in just O(log log n) rounds. Or, by choosing D nc= p log n the algorithm will compute a (D= p log n)-colouring in O( p log n) rounds. Notice also that the algorithm works for k = (logD), thereby matching the lower bounds of Bollobas and the existential statements of Johansson and Kim. It should be pointed out however that our statement is weaker than their existential statement insofar as it needs the additional assumption D = (logn). This, as well as the regularity assumption (also assumed in [9, 14]), might in fact be an artifact of our analysis which relies on large deviation inequalities that cease to give strong enough bounds for lower values of D. Although we stated our result in its most general form, in this abstract we shall present a slightly weaker version, due to lack of space. Namely, we shall show that the above statement holds with the running timereplaced by O(log n).
