Talk:Arboricity

Recent redefinition by Phaunt

Phaunt (talk · contribs) changed the lede sentence to read "The arboricity of an undirected graph is the size of the minimum forest into which its edges can be partitioned." I believe it is wrong in multiple ways, so I reverted, but it may be worth more discussion here.

• First, if a graph has cycles, its edges cannot be partitioned into a single forest. A forest is a single graph with no cycles, or equivalently the disjoint union of trees. If one partitions the edges of a cyclic graph into disjoint trees, the trees are not disjoint, so it is not a forest.
• Second, the "size" of a forest is unclear and it is not obvious that it refers to the number of trees.
• Third, the number of trees into which the edges of a graph can be partitioned is not the same as arboricity. Consider, e.g., a dumbell graph formed by two cycles connected by a single bridge edge. Its arboricity is two (it is easy to partition the edges into two forests: just make one forest consist of an edge from each cycle, and the other forest consist of all the rest of the edges) but if one tries to partition its edges into trees, three trees are required.

—David Eppstein 03:15, 15 August 2007 (UTC)

The example picture seems incorrect. The middle green edge is disconnected and should actually be blue. — Preceding unsigned comment added by 193.43.246.250 (talk • contribs)

No, it's correct. For arboricity, the problem is to partition the edges of the graph into forests; they don't have to be connected. Partitioning the edges into connected trees (that might not span all the vertices) is a different and much harder problem. —David Eppstein (talk) 15:50, 27 May 2014 (UTC)

Recent changes to algorithms section

It was claimed that there is a near-linear time algorithm with an additive error of 2. This is not true, since the paper has a complexity of $O(m\log n\Gamma \log ^{*}\Gamma )$ (notice the $\Gamma$ is not inside $\log$). As mentioned by the authors, it is only slightly better than the known $O(m{\sqrt {m}}\log(n^{2}/m))$ algorithm. MahdiJafariRaviz (talk) 17:57, 9 June 2025 (UTC)

Thanks for catching this and for providing the more detailed explanation here. —David Eppstein (talk) 19:42, 9 June 2025 (UTC)

References