Decomposing a planar graph with girth 9 into a forest and a matching (Q925026)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5280763
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Decomposing a planar graph with girth 9 into a forest and a matching |
scientific article; zbMATH DE number 5280763 |
Statements
Decomposing a planar graph with girth 9 into a forest and a matching (English)
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
0.9624671339988708
0 references
0.956488311290741
0 references
0.8845659494400024
0 references
0.8439554572105408
0 references
0.8104615807533264
0 references
