Decompositions of quadrangle-free planar graphs

Oleg V. Borodin, Anna O. Ivanova, Alexandr V. Kostochka, Naeem N. Sheikh

Research output: Contribution to journalArticlepeer-review

Abstract

Research supported in part by the RFBR grants 08-01-00673 and 06-01-00694. Research supported in part by the RFBR grants 08-01-00673 and 06-01-00694. Research supported in part by NSF grant DMS-0650784 and the RFBR grant 06-01-00694. abs W. He et al. showed that a planar graph not containing 4-cycles can be decomposed into a forest and a graph with maximum degree at most 7. This degree restriction was improved to 6 by Borodin et al. We further lower this bound to 5 and show that it cannot be improved to 3.

Original languageEnglish (US)
Pages (from-to)87-99
Number of pages13
JournalDiscussiones Mathematicae - Graph Theory
Volume29
Issue number1
DOIs
StatePublished - 2009

Keywords

  • Graph decompositions
  • Planar graphs
  • Quadrangle-free graphs

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Decompositions of quadrangle-free planar graphs'. Together they form a unique fingerprint.

Cite this