ABSTRACT
We now review the concept of the arboricity of a graph. This invariant plays a significant role in bounding the complexity of certain algorithms. For example, we will soon have need to find all squares or triangles of a graph G. These tasks can be accomplished with relatively simple algorithms whose running time is bounded by O
(|V (G)| · a(G)), where a(G) is the arboricity of G. As a(G) is quite small for many of the graphs we consider (such as subgraphs of hypercubes), these methods lead to significant improvements in running time.
