Arboricity

The arboricity of a finite simple graph is the minimum number of edge-disjoint acyclic subgraphs (i.e., spanning forests) whose edge sets partition the edge set of . It is the covering version of the packing invariant anarboricity (Harary and Palmer 1973a, p. 225). An edgeless graph has arboricity 0. For with at least two vertices, Nash-Williams (1964) showed that

(1)

where is the edge count, is the vertex count of a subgraph , and is the ceiling function.

Writing for the maximum average degree and for the pseudoarboricity, a lower bound is

(2)

The pseudoarboricity is the minimum number of pseudoforests whose edge sets partition the edge set of ; each connected component of a pseudoforest has at most one cycle. In general, . For example, the lower bound is attained by every forest and every complete graph of even vertex count. For a cycle graph with , while , so connectedness alone does not imply equality.

For a graph with at least two vertices,

(3)

where is the edge count and is the vertex count (Nash-Williams 1964).

This bound immediately gives a number of useful lower bounds. If is the graph degeneracy of , then , so

(4)

This bound is often very quick to evaluate, although it need not be sharp. A stronger lower bound is obtained by repeatedly deleting a vertex of minimum vertex degree and considering the resulting chain of residual subgraphs

(5)

Then

(6)

is also a lower bound for the arboricity, since each is a subgraph of . This peeling bound is always at least as large as , but it is not exact in general, because a densest witness subgraph need not occur along a single minimum vertex degree peeling chain. For example, the bishop graph on a board has peeling bound 3 but arboricity 4, the bishop graph on an board has peeling bound 5 but arboricity 6, and the camel graph on a board has peeling bound 2 but arboricity 3.

An acyclic graph with at least one graph edge therefore has . Furthermore, the arboricity of a planar graph is at most 3 (Harary 1994, p. 124, Problem 11.22).

For a graph on vertices, let be the maximum edge count of a subgraph with vertices. Then

(7)

(Nash-Williams 1964; Harary 1994, p. 90).

The arboricity of the complete graph , for , is given by

(8)

of the complete bipartite graph , for positive integers and , by

(9)

(Harary 1994, p. 91), and of the complete tripartite graph , for positive integers , , and , by

(10)

For positive integers , , ..., with , the arboricity of the complete multipartite graph is

(11)

Equivalently, writing for the vertex count,

(12)