A short proof of Nash-Williams' theorem for the arboricity of a graph

DOI10.1007/BF01202467MaRDI QIDQ1323488zbMATH OpenFDO

Authors Boliong Chen, Makoto Matsumoto, Jianfang Wang, Zhongfu Zhang, Jianxun Zhang

Publication date 10 May 1994

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01202467

zbMATH Keywords

decompositionedge-arboricityNash-Williams' theoremspanning trees

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

The authors give a self-contained short proof of Nash-Williams' formula \[ \rho(G)= \max_{H< G} \lceil q(H)/(p(H)- 1)\rceil \] for the edge- arboricity \(\rho(G)\) of a graph (with possible multiple edges but no loops). Here \(H\) runs over all subgraphs of \(G\) with \(p(H)= \# V(H)> 1\) and \(q(H)= \# E(H)\). The proof easily follows from the following lemma which is proved in detail. Lemma: Let \(G\) be a connected arboricity critical graph with \(p(G)> 1\). Then for any \(e\in E(G)\), any \((\rho(G)-1)\)-forest decomposition of \(G-e\) is a decomposition into \(\rho(G)-1\) spanning trees of \(G\).

Recommendations

• scientific article; zbMATH DE number 221058
• An enhancement of Nash-Williams' theorem on edge arboricity of graphs
• A short proof of Brooks’ Theorem for vertex arboricity
• Nash-Williams' theorem on decomposing graphs into forests
• scientific article; zbMATH DE number 3873386
• A note on the arboricity of graphs
• Short proofs of theorems of Nash-Williams and Tutte
• A short proof of a theorem on degree sets of graphs
• A graph-theoretic proof of arrow's dictator theorem
• The Nash-Williams conjecture and the dominating cycle conjecture

Cites work

• Decomposition of Finite Graphs Into Forests
• Edge-Disjoint Spanning Trees of Finite Graphs
• scientific article; zbMATH DE number 221058 (Why is no real title available?)

Cited in

(13)

• A note on the arboricity of graphs
• Simple planar graph partition into three forests
• Extensions of matroid covering and packing
• An enhancement of Nash-Williams' theorem on edge arboricity of graphs
• Arboricity and tree-packing in locally finite graphs
• Short proofs of theorems of Nash-Williams and Tutte
• Fast approximation for computing the fractional arboricity and extraction of communities of a graph
• Nash-Williams' theorem on decomposing graphs into forests
• Self-stabilizing Cuts in Synchronous Networks
• scientific article; zbMATH DE number 221058 (Why is no real title available?)
• A short proof of Brooks’ Theorem for vertex arboricity
• A short proof of the random Ramsey theorem
• A self-stabilizing algorithm for cut problems in synchronous networks

This page was built for publication: A short proof of Nash-Williams' theorem for the arboricity of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1323488)