Partitioning a planar graph of girth 10 into a forest and a matching

A. Bassa, J. Burns, J. Campbell, A. Deshpande, J. Farley, M. Halsey, S. Y. Ho, D. Kleitman, S. Michalakis, P. O. Persson, P. Pylyavskyy, L. Rademacher, A. Riehl, M. Rios, J. Samuel, B. E. Tenner, A. Vijayasarathy, L. Zhao

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)213-228
Number of pages16
JournalStudies in Applied Mathematics
Volume124
Issue number3
DOIs
StatePublished - Apr 2010

Fingerprint Dive into the research topics of 'Partitioning a planar graph of girth 10 into a forest and a matching'. Together they form a unique fingerprint.

Cite this