Decomposing a planar graph with girth 9 into a forest and a matching (Q925026)

From MaRDI portal
Revision as of 01:38, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
Decomposing a planar graph with girth 9 into a forest and a matching
scientific article

    Statements

    Decomposing a planar graph with girth 9 into a forest and a matching (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    29 May 2008
    0 references
    A decomposition of a graph is a partitioning of the edge set. The authors show that any planar graph of girth 9 has a decomposition such that one part is a forest and the second part is a matching. This was previously known for planar graphs of girth 11, subsequently improved to girth 10. It is an open question if any planar graph of girth 8 decomposes into a forest and a matching. This is related to results such as a planar graph of girth 6 can be decomposed into a forest and a graph with maximum degree 2, and a planar graph can be decomposed into 3 forests such that one forest has maximum degree at most 8.
    0 references
    decomposition
    0 references
    planar
    0 references

    Identifiers