Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-10T05:00:14.186Z Has data issue: false hasContentIssue false
  • English
  • Français

NASH-WILLIAMS’ THEOREM ON DECOMPOSING GRAPHS INTO FORESTS

Part of: Graph theory

Published online by Cambridge University Press:  06 August 2013

Christian Reiher  and
Lisa Sauermann
Christian Reiher
Affiliation:
Mathematisches Seminar der Universität Hamburg, Bundesstrasse 55, D-20146 Hamburg,Germany email Christian.Reiher@uni-hamburg.de
Lisa Sauermann
Affiliation:
Rheinische Friedrich-Wilhelms-Universität Bonn, Endenicher Allee 60, 53115 Bonn, Germany email Lisa.Sauermann@web.de

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We give a simple graph-theoretic proof of a classical result due to Nash-Williams on covering graphs by forests. Moreover, we derive a slight generalization of this statement where some edges are preassigned to distinct forests.

MSC classification

Secondary: 05C70: Factorization, matching, partitioning, covering and packing

Information

Type
Research Article
Information
Mathematika , Volume 60 , Issue 1 , January 2014 , pp. 32 - 36
Copyright
Copyright © University College London 2013 

References

Chen, B., Matsumoto, M., Wang, J., Zhang, Z. and Zhang, J., A short proof of Nash-Williams’ theorem for the arboricity of a graph. Graphs Combin. 10 (1994), 27–28.CrossRefGoogle Scholar
Nash-Williams, C. St. J. A., Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. 36 (1961), 445–450.Google Scholar
Nash-Williams, C. St. J. A., Decomposition of finite graphs into forests. J. Lond. Math. Soc. 39 (1964), 12.Google Scholar
Tutte, W. T., On the problem of decomposing a graph into $n$ connected factors. J. Lond. Math. Soc. 36 (1961), 221–230.CrossRefGoogle Scholar
http://www.artofproblemsolving.com/Forum/resources.php?c=143&cid=61&year=2007.Google Scholar