Decomposing a planar graph with girth 9 into a forest and a matching
type: Item
instance of: scholarly article
title: Decomposing a planar graph with girth 9 into a forest and a matching
zbMATH Open document ID: 1144.05019
author: Oleg V. Borodin
author: Alexandr Kostochka
author: Naeem N. Sheikh
author: Gexin Yu
published in: European Journal of Combinatorics
publication date: 2008-05-29T00:00:00Z
review text: 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.
reviewed by: Dan S. Archdeacon
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 5280763
zbMATH Keywords: decomposition
zbMATH Keywords: planar
MaRDI profile type: Publication
full work available at URL: j.ejc.2007.06.020
OpenAlex ID: W1984593473
Wikidata QID: Q60060259
cites work: Covering planar graphs with forests
cites work: Edge-partitions of planar graphs and their game coloring numbers
DOI: 10.1016/J.EJC.2007.06.020
description: scientific article; zbMATH DE number 5280763