The paper deals with distributed solutions of graph problems. The model assumes that each node of the graph is occupied by a processor that has a unique ID number. Moreover, the computation is reliable, synchronous, and communication is accomplished by message passing along the edges of the graph. Let \(\text{diam}(G)\) denote the diameter of the graph \(G\). Since \(O(\text{diam}(G))\) time suffices to store the entire graph (with its corresponding processor ID) in each processor's memory, the author is interested in problems that can be solved faster than \(\text{diam}(G)\). The main results are the following. (a) A 3-coloring of an \(n\)-cycle requires time \(\Omega(\log^* n)\). (b) Any algorithm for coloring a \(d\)-regular tree of radius \(r\) which runs for time at most \(2r/3\), requires at least \(\Omega(\sqrt d)\) colors. (c) In an \(n\)-vertex graph with largest degree \(\Delta\), an \(O(\Delta^ 2)\)-coloring can be found in time \(O(\log^* n)\).