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)
|
Related parameters change either the permitted edge parts or the set being partitioned. The following table summarizes the variants and the related packing parameter covered here.
| parameter | description |
| anarboricity | maximum number of cyclic edge parts (for a cyclic graph) |
| fractional arboricity | fractional relaxation of covering the edge set by forests |
| linear arboricity | minimum number of forests of paths partitioning the edge set |
| pseudoarboricity | minimum number of pseudoforests partitioning the edge set |
| star arboricity | minimum number of forests of stars partitioning the edge set |
| vertex arboricity | minimum number of vertex parts, each inducing a forest |