A theorem of Brooks guarantees that a maximum-degree-D graph can be properly colored with D colors if the graph does not contain a large complete subgraph. It is proved that finding such a coloring is in NC.

Let $w \in (0 + 1)^*$ be a finite nonempty string of zeros and ones, and let $a_w (n)$ denote the number of (possibly overlapping) occurrences of w in the binary expansion of n. Allouche and Shallit have recently shown that there exists an effectively computable rational function $b_w (n)$ such that \[ \sum_{n\geqq 0} \log_2 (b_w (n))X^{a_w (n)} = \frac{1}{X - 1} \] for all complex X such that $| X |\leqq 1$ and $X \ne 1$. They gave an algorithm to determine $b_w (n)$. It is shown that the algorithm to determine $b_w (n)$ is related to a certain labeled binary tree $T(w)$. This observation allows two identities to be proven for the rational functions $b_w (n)$. Combinatorial methods are used to investigate the structure of the tree $T(w)$. As the running time of the algorithm is proportional to the total number of nodes in the tree $T(w)$, the algorithm in this paper is shown to run in polynomial time by proving that $|T(w)| =O(|w|^{11.1})$. The existence of infinitely many strings w such that $| T(w) |\geqq c| w |^3 $ is also shown.

G.A. Dirac's classical theorem (1952) asserts that if every vertex of a graph G on n vertices has degree at least n/2, the G has a Hamiltonian cycle. A fast parallel algorithm on a concurrent-read-exclusive-write parallel random-access machine (CREW PRAM) is given to find a Hamiltonian cycle in such graphs. The algorithm uses a linear number of processors and is optimal up to a polylogarithmic factor. It works in O(log/sup 4/n) parallel time and uses linear number of processors on a CREW PRAM. It is also proved that a perfect matching in dense graphs can be found in NC/sup 2/. The cost of improved time is a quadratic number of processors. It is also proved that finding an NC algorithm for perfect matching in slightly less dense graphs is as hard as the same problem for all graphs, and the problem of finding a Hamiltonian cycle becomes NP-complete.>

The first result concerns branching programs having width (log n) °{*).We give an fl(n log n~ log log n) lower bound for the size of such branching programs computing almost any symmetric Boolean fnnction and in particular the following explicit fnnction: "the sum of the input variables is a quadratic residue mod p" where p is any given prime between n 1/4 and n 1/3.This is a strengthening of previous nonlinear lower bounds obtained by Chandra, Furst, Lipton and by Pudlgk.We mention that by iterating our method the result can be further strengthened to lfl(nlog n).The second result is a C" lower bound for read-onceonly branching programs computing an explicit Boolean function.For n = (~), the function computes the parity of the number of triangles in a graph on v vertices.This improves previous exp(cx/n ) lower bounds for other graph functions by Wegener and Z£k.The result implies a linear lower bound for the space complexity of this Boolean function on "eraser machines", i.e. machines that erase each input bit immediately after having read it.