Decomposing a planar graph with girth 9 into a forest and a matching (Q925026): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q60060259, #quickstatements; #temporary_batch_1711486624475 |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Covering planar graphs with forests / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Edge-partitions of planar graphs and their game coloring numbers / rank | |||
Normal rank | |||
Latest revision as of 10:05, 28 June 2024
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
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
