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 language | English (US) |
---|---|
Pages (from-to) | 87-99 |
Number of pages | 13 |
Journal | Discussiones Mathematicae - Graph Theory |
Volume | 29 |
Issue number | 1 |
DOIs | |
State | Published - 2009 |
Keywords
- Graph decompositions
- Planar graphs
- Quadrangle-free graphs
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics