Premium
Partitioning a Planar Graph of Girth 10 into a Forest and a Matching
Author(s) -
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.
Publication year - 2010
Publication title -
studies in applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 46
eISSN - 1467-9590
pISSN - 0022-2526
DOI - 10.1111/j.1467-9590.2009.00468.x
Subject(s) - girth (graph theory) , mathematics , planar , combinatorics , graph , planar graph , matching (statistics) , discrete mathematics , computer science , statistics , computer graphics (images)
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.