Summary: The advent of multiprocessor computing systems, the development of parallel programming, and the theory of high-power computer design have simulated rigorous research into parallel algorithms and their complexity. As with sequential algorithms, the researchers mainly focused on topics in discrete mathematics (sorting, search, etc.). Graph- theoretical problems are of interest not only because of their visibility and fairly detailed level of research in the sequential case, but also because of their many applications and uses. In this article, we review some of the results relating to parallel computations on graphs.