# Arboricity

__: Number of forests a graph's edges may be partitioned into__

**Short description**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. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is *k*-arboric.

## Example

The figure shows the complete bipartite graph *K*_{4,4}, with the colors indicating a partition of its edges into three forests. *K*_{4,4} cannot be partitioned into fewer forests, because any forest on its eight vertices has at most seven edges, while the overall graph has sixteen edges, more than double the number of edges in a single forest. Therefore, the arboricity of *K*_{4,4} is three.

## Arboricity as a measure of density

The arboricity of a graph is a measure of how dense the graph is: graphs with many edges have high arboricity, and graphs with high arboricity must have a dense subgraph.

In more detail, as any n-vertex forest has at most n-1 edges, the arboricity of a graph with n vertices and m edges is at least [math]\displaystyle{ \lceil m/(n-1)\rceil }[/math]. Additionally, the subgraphs of any graph cannot have arboricity larger than the graph itself, or equivalently the arboricity of a graph must be at least the maximum arboricity of any of its subgraphs. Nash-Williams proved that these two facts can be combined to characterize arboricity: if we let n_{S} and m_{S} denote the number of vertices and edges, respectively, of any subgraph S of the given graph, then the arboricity of the graph equals [math]\displaystyle{ \max_S\{\lceil m_S/(n_S-1)\rceil\}. }[/math]

Any planar graph with [math]\displaystyle{ n }[/math] vertices has at most [math]\displaystyle{ 3n-6 }[/math] edges, from which it follows by Nash-Williams' formula that planar graphs have arboricity at most three. Schnyder used a special decomposition of a planar graph into three forests called a **Schnyder wood** to find a straight-line embedding of any planar graph into a grid of small area.

## Algorithms

The arboricity of a graph can be expressed as a special case of a more general matroid partitioning problem,^{[1]} in which one wishes to express a set of elements of a matroid as a union of a small number of independent sets. As a consequence, the arboricity can be calculated by a polynomial-time algorithm (Gabow Westermann). The current best exact algorithm computes the arboricity in [math]\displaystyle{ O(m \sqrt{m}) }[/math] time, where [math]\displaystyle{ m }[/math] is the number of edges in the graph.

Approximations to the arboricity of a graph can be computed faster. There are linear time 2-approximation algorithms,^{[2]}^{[3]} and a near-linear time algorithm with an additive error of 2.^{[4]}

## Related concepts

The **anarboricity** of a graph is the maximum number of edge-disjoint nonacyclic subgraphs into which the edges of the graph can be partitioned.

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 graph can be partitioned. 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.

The **linear arboricity** of a graph is the minimum number of linear forests (a collection of paths) into which the edges of the graph can be partitioned. The linear arboricity of a graph is closely related to its maximum degree and its slope number.

The **pseudoarboricity** of a graph is the minimum number of pseudoforests into which its edges can be partitioned. Equivalently, it is the maximum ratio of edges to vertices in any subgraph of the graph, rounded up to an integer. As with the arboricity, the pseudoarboricity has a matroid structure allowing it to be computed efficiently (Gabow Westermann).

The **subgraph density** of a graph is the density of its densest subgraph.

The **thickness** of a graph is the minimum number of planar subgraphs into which its edges can be partitioned. As any planar graph has arboricity three, the thickness of any graph is at least equal to a third of the arboricity, and at most equal to the arboricity.

The **degeneracy** of a graph is the maximum, over all induced subgraphs of the graph, of the minimum degree of a vertex in the subgraph. The degeneracy of a graph with arboricity [math]\displaystyle{ a }[/math] is at least equal to [math]\displaystyle{ a }[/math], and at most equal to [math]\displaystyle{ 2a-1 }[/math]. The coloring number of a graph, also known as its Szekeres-Wilf number (Szekeres Wilf) is always equal to its degeneracy plus 1 (Jensen Toft).

The **strength** of a graph is a fractional value whose integer part gives the maximum number of disjoint spanning trees that can be drawn in a graph. It is the packing problem that is dual to the covering problem raised by the arboricity. The two parameters have been studied together by Tutte and Nash-Williams.

The **fractional arboricity** is a refinement of the arboricity, as it is defined for a graph [math]\displaystyle{ G }[/math] as [math]\displaystyle{ \max\{m_S/(n_S-1) \mid S \subseteq G\}. }[/math] In other terms, the arboricity of a graph is the ceiling of the fractional arboricity.

The **(a,b)-decomposability** generalizes the arboricity. A graph is [math]\displaystyle{ (a,b) }[/math]-decomposable if its edges can be partitioned into [math]\displaystyle{ a+1 }[/math] sets, each one of them inducing a forest, except one who induces a graph with maximum degree [math]\displaystyle{ b }[/math]. A graph with arboricity [math]\displaystyle{ a }[/math] is [math]\displaystyle{ (a,0) }[/math]-decomposable.

The **tree number** is the minimal number of trees covering the edges of a graph.

## Special appearances

Arboricity appears in the Goldberg–Seymour conjecture.

## References

- ↑ Edmonds, Jack (1965), "Minimum partition of a matroid into independent subsets",
*Journal of Research of the National Bureau of Standards Section B***69B**: 67, doi:10.6028/jres.069B.004 - ↑ Eppstein, David (1994), "Arboricity and bipartite subgraph listing algorithms",
*Inf. Process. Lett.***51**(4): 207–211, doi:10.1016/0020-0190(94)90121-X - ↑ Arikati, Srinivasa Rao; Maheshwari, Anil; Zaroliagis, Christos D. (1997), "Efficient computation of implicit representations of sparse graphs",
*Discrete Appl. Math.***78**(1–3): 1–16, doi:10.1016/S0166-218X(97)00007-3 - ↑ Blumenstock, Markus; Fischer, Frank (2020), "A constructive arboricity approximation scheme",
*46th International Conference on Current Trends in Theory and Practice of Informatics*

- Alon, N. (1988). "The linear arboricity of graphs".
*Israel Journal of Mathematics***62**(3): 311–325. doi:10.1007/BF02783300. - Chen, B.; Matsumoto, M.; Wang, J.; Zhang, Z.; Zhang, J. (1994). "A short proof of Nash-Williams' theorem for the arboricity of a graph".
*Graphs and Combinatorics***10**(1): 27–28. doi:10.1007/BF01202467. - Erdős, P.; Hajnal, A. (1966). "On chromatic number of graphs and set-systems".
*Acta Mathematica Hungarica***17**(1–2): 61–99. doi:10.1007/BF02020444. - Gabow, H. N.; Westermann, H. H. (1992). "Forests, frames, and games: Algorithms for matroid sums and applications".
*Algorithmica***7**(1): 465–497. doi:10.1007/BF01758774. - Hakimi, S. L.; Mitchem, J.; Schmeichel, E. E. (1996). "Star arboricity of graphs".
*Discrete Mathematics***149**(1–3): 93–98. doi:10.1016/0012-365X(94)00313-8. - Jensen, T. R.; Toft, B. (1995).
*Graph Coloring Problems*. New York: Wiley-Interscience. ISBN 0-471-02865-7. - C. St. J. A. Nash-Williams (1961). "Edge-disjoint spanning trees of finite graphs".
*Journal of the London Mathematical Society***36**(1): 445–450. doi:10.1112/jlms/s1-36.1.445. - C. St. J. A. Nash-Williams (1964). "Decomposition of finite graphs into forests".
*Journal of the London Mathematical Society***39**(1): 12. doi:10.1112/jlms/s1-39.1.12. - W. Schnyder (1990). "Embedding planar graphs on the grid". pp. 138–148. http://portal.acm.org/citation.cfm?id=320176.320191.
- Szekeres, G.; Wilf, H. S. (1968). "An inequality for the chromatic number of a graph".
*Journal of Combinatorial Theory***4**: 1–3. doi:10.1016/s0021-9800(68)80081-x. - Tutte, W. T. (1961). "On the problem of decomposing a graph into n connected factors".
*Journal of the London Mathematical Society***36**(1): 221–230. doi:10.1112/jlms/s1-36.1.221.

Original source: https://en.wikipedia.org/wiki/Arboricity.
Read more |