Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-26T07:21:38.622Z Has data issue: false hasContentIssue false

NASH-WILLIAMS’ THEOREM ON DECOMPOSING GRAPHS INTO FORESTS

Published online by Cambridge University Press:  06 August 2013

Christian Reiher
Affiliation:
Mathematisches Seminar der Universität Hamburg, Bundesstrasse 55, D-20146 Hamburg,Germany email [email protected]
Lisa Sauermann
Affiliation:
Rheinische Friedrich-Wilhelms-Universität Bonn, Endenicher Allee 60, 53115 Bonn, Germany email [email protected]
Get access

Abstract

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.

Type
Research Article
Copyright
Copyright © University College London 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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), 2728.CrossRefGoogle Scholar
Nash-Williams, C. St. J. A., Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. 36 (1961), 445450.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), 221230.CrossRefGoogle Scholar