Partitioning a Planar Graph of Girth 10 into a Forest and a Matching

We prove that any finite planar graph with girth at least 10 can have its edges partitioned to form two graphs on the same vertices, one of which is a forest, and the other of which is a matching. Several related results are also demonstrated.

Saved in:
Bibliographic Details
Published in:Studies in applied mathematics (Cambridge) 2010-04, Vol.124 (3), p.213-228
Main Authors: Bassa, A., Burns, J., Campbell, J., Deshpande, A., Farley, J., Halsey, M., Ho, S.-Y., Kleitman, D., Michalakis, S., Persson, P.-O., Pylyavskyy, P., Rademacher, L., Riehl, A., Rios, M., Samuel, J., Tenner, B. E., Vijayasarathy, A., Zhao, L.
Format: Article
Language:English
Subjects:
Forests
Graphs
Matching
Mathematical analysis
Mathematics
Partitioning
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We prove that any finite planar graph with girth at least 10 can have its edges partitioned to form two graphs on the same vertices, one of which is a forest, and the other of which is a matching. Several related results are also demonstrated.
ISSN:0022-2526
1467-9590
DOI:10.1111/j.1467-9590.2009.00468.x