Arboricity

The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph.

Read more about Arboricity:  Example, Arboricity As A Measure of Density, Algorithms, Related Concepts

Other articles related to "arboricity":

Arboricity - Related Concepts
... The star arboricity of a graph is the size of the minimum forest, each tree of which is a star (tree with at most one non-leaf node), into which the edges of the ... If a tree is not a star itself, its star arboricity is two, as can be seen by partitioning the edges into two subsets at odd and even distances from the tree root respectively ... Therefore, the star arboricity of any graph is at least equal to the arboricity, and at most equal to twice the arboricity ...
Clique Problem - Algorithms - Cliques of Fixed Size
... time for this algorithm is proportional to the arboricity of the graph (a(G)) times the number of edges, which is O(m a(G)) ... Since the arboricity is at most O(m1/2), this algorithm runs in time O(m3/2) ... takes time proportional to the number of edges times the (k − 2)nd power of the arboricity ...