Decomposing a planar graph with girth 9 into a forest and a matching (Q925026): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/j.ejc.2007.06.020 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W1984593473 / rank | |||
Normal rank | |||
| Property / Wikidata QID | |||
| Property / Wikidata QID: Q60060259 / rank | |||
Normal rank | |||
| 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
