(a, b)-decomposition¶
An (a, b)-decomposition assigns a graph's edges to a specified number a of forest parts and one residual part of maximum degree at most b.
Core Idea¶
An (a, b)-decomposition assigns every edge of a finite undirected graph to exactly one of a forest parts or one residual part whose maximum within-part vertex degree is at most b. The forest parts must be acyclic; the ordinary residual may have cycles. If the residual is also a forest, the assignment meets the stronger F(a, b) condition. The parameters describe an individual edge assignment, while a theorem saying every graph in a class admits it makes a further claim.[^ref-ba50f6e522ab]
Gonçalves states related (t,D) coverability and F(d₁,…,dₖ) conditions. His planar proof constructs an edge partition; a qualifying cover can also be refined by assigning a multiply covered edge once, because deleting edges preserves acyclicity and cannot increase the residual degree. This partition refinement is an editorial inference, not the wording of his coverability definition.[^ref-ba50f6e522ab]
Scope of Application¶
Use this entry for edge decomposition, not vertex partition. Gonçalves proves that every planar graph has an F(2,4) decomposition: two forests and a third forest of maximum degree four. He also reports planar graphs not (2,3)-coverable, so a full-class two-forest guarantee cannot simply lower the residual cap to three. Wang and Zhang's publisher abstract gives a different class result: every planar graph of girth at least eight decomposes into a forest and a matching, hence F(1,1); it reports girth-seven counterexamples to that universal statement.[ref-ba50f6e522ab][ref-893825bb176e]
These theorems have exact graph-class hypotheses. A single wheel or cycle assignment below proves only its own case, not the all-planar or all-girth-eight claim.
Clarity¶
Write E(G)=F₁ ⊔ … ⊔ Fₐ ⊔ B. Check each Fᵢ for cycles, B for Δ(B)≤b, and the parts together for disjoint coverage. Degree is counted within B, so a high-degree vertex of G may be harmless after its edges are distributed. A residual with degree at most two can still be cyclic, which is why (a,b) and F(a,b) differ.[^ref-ba50f6e522ab]
For example, in K₄ put the three edges incident to vertex 4 in a star forest and the other three edges in a triangle. That displayed assignment is (1,2) but not F(1,2) because the residual triangle is cyclic. It does not prove that K₄ has no other assignment satisfying F(1,2).
Manages Complexity¶
The partition turns a graph-wide edge question into local checks: acyclicity in each forest, maximum degree in the residual, and complete one-time edge assignment. The five-vertex wheel can place its four hub edges in a bounded-degree star while dividing the rim between two forests. The eight-cycle can break its sole cycle by leaving one edge as a matching remainder. These displayed checks are straightforward; proving a guarantee for every graph in a planar class is a separate, harder result.[ref-ba50f6e522ab][ref-893825bb176e]
Abstract Reasoning¶
For a proposed (a,b) assignment, test coverage and disjointness first, then each forest and the residual degree bound. Test residual acyclicity only if the stronger F(a,b) label is used. If one displayed partition fails, another partition might still work. For a class claim, state whether the graph is merely planar or also has the required girth, and use the theorem with its exact quantifier. Girth-seven counterexamples limit Wang–Zhang's all-graphs-in-class guarantee; they do not say every girth-seven graph fails.[ref-ba50f6e522ab][ref-893825bb176e]
Knowledge Transfer¶
The wheel and cycle below use the same edge-partition test with unlike structures and parameters: F(2,4) versus F(1,1). Their disjoint-and-exhaustive edge assignment presupposes live Partition of a Set, and reaches Prime Partition through that parent. Forest acyclicity and within-part vertex degree remain graph-specific. Arboricity is related to the zero-residual all-forest case; Matching describes the degree-one remainder, not every positive-b remainder.[ref-ba50f6e522ab][ref-893825bb176e]
Example¶
Five-vertex wheel. Let the four-cycle rim have edges 12,23,34,41 and hub c have edges c1,c2,c3,c4. Assign F₁={12,23,34}, F₂={41}, and B={c1,c2,c3,c4}. The first two are forests, B is a star with Δ(B)=4, and the three parts contain each of the eight edges once. The same assignment is F(2,4) because the residual star is acyclic. Mapped back: wheel edges are the carrier; two rim forests give a=2; the hub star gives b=4; the disjoint union verifies the assignment. This is a curator construction, while Gonçalves Theorem 1 separately proves the all-planar class result.[^ref-ba50f6e522ab]
Eight-cycle. Let C₈ have edges 12,23,34,45,56,67,78,81. Assign the first seven edges to a path forest and {81} to a one-edge matching. Together they cover C₈ once; the matching is an acyclic residual of maximum degree one, so this is F(1,1). Mapped back: cycle edges are the carrier; the path supplies a=1; the matching supplies b=1; disjoint coverage completes the test. This curator construction is one graph within, not a proof of, Wang–Zhang's all-planar-girth-at-least-eight result.[^ref-893825bb176e]
Relationships to Other Abstractions¶
Current abstraction (a, b)-decomposition Domain-specific
Parents (1) — more general patterns this builds on
-
(a, b)-decomposition presupposes Partition of a set Domain-specific
The realized edge parts must be disjoint and cover the graph's entire edge set.
Hierarchy path (1) — routes to 1 parentless root
- (a, b)-decomposition → Partition of a set → Partition → Set and Membership
Neighborhood in Abstraction Space¶
(a, b)-decomposition sits in a sparse region of the domain-specific corpus (64th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Graph Classes & Invariants (37 abstractions)
Nearest neighbors
- Cyclomatic number — 0.86
- Graph factorization — 0.84
- Double graph — 0.84
- Friendly-index set — 0.84
- Quartic graph — 0.84
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
A vertex partition divides V(G), whereas this object assigns edges. A cover may overlap until refined to a partition. F(a,b) additionally requires residual acyclicity. Arboricity measures the fewest all-forest layers, not a displayed assignment with a bounded residual. Forest plus matching is the F(1,1) special case. Finally, the failure of one assignment and the failure of a universal class guarantee are different claims.[ref-ba50f6e522ab][ref-893825bb176e]
References¶
[^ref-ba50f6e522ab]: D. Gonçalves, “Covering planar graphs with degree bounded forests,” author-hosted preprint, Introduction PDF p. 0 for (t,D) and F(d₁,…,dₖ) coverability and the cited prior planar bounds; Theorem 1 PDF p. 1 for F(∞,∞,4); explicit edge-partition conclusion PDF p. 3. Cover-to-partition refinement and the displayed wheel/K₄ assignments are editorial inferences, not examples quoted from the paper. https://www.lirmm.fr/~goncalves/pmwiki/uploads/boundedforest.pdf
[^ref-893825bb176e]: Yingqian Wang and Qijun Zhang, “Decomposing a planar graph with girth at least 8 into a forest and a matching,” Discrete Mathematics 311 (2011), 844–849, DOI 10.1016/j.disc.2011.01.019, publisher abstract for the girth-eight result and girth-seven counterexamples. Full article proof and individual drawings were not consulted; the displayed eight-cycle assignment is an editorial construction. https://www.sciencedirect.com/science/article/pii/S0012365X1100029X