Partitioning a Planar Graph of Girth 10 into a Forest and a Matching
A. Bassa, Jason Matthew Burns, J. W. Campbell, Ajay Deshpande, Jonathan David Farley, Mark D. Halsey, S.-Y. Ho, Daniel J. Kleitman, Spyridon Michalakis, Per‐Olof Persson, Pavlo Pylyavskyy, Luis Rademacher, Amanda Riehl, Mauricio Flores Rios, Javed K. K Samuel, Bridget Eileen Tenner, A. Vijayasarathy, Liang Zhao · Studies in Applied Mathematics · 2010
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.