# Decompositions of quadrangle-free planar graphs

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

Discussiones Mathematicae Graph Theory (2009)

- Volume: 29, Issue: 1, page 87-99
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topOleg V. Borodin, et al. "Decompositions of quadrangle-free planar graphs." Discussiones Mathematicae Graph Theory 29.1 (2009): 87-99. <http://eudml.org/doc/270206>.

@article{OlegV2009,

abstract = {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.},

author = {Oleg V. Borodin, Anna O. Ivanova, Alexandr V. Kostochka, Naeem N. Sheikh},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {planar graphs; graph decompositions; quadrangle-free graphs},

language = {eng},

number = {1},

pages = {87-99},

title = {Decompositions of quadrangle-free planar graphs},

url = {http://eudml.org/doc/270206},

volume = {29},

year = {2009},

}

TY - JOUR

AU - Oleg V. Borodin

AU - Anna O. Ivanova

AU - Alexandr V. Kostochka

AU - Naeem N. Sheikh

TI - Decompositions of quadrangle-free planar graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2009

VL - 29

IS - 1

SP - 87

EP - 99

AB - 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.

LA - eng

KW - planar graphs; graph decompositions; quadrangle-free graphs

UR - http://eudml.org/doc/270206

ER -

## References

top- [1] A. Bassa, J. Burns, J. Campbell, A. Deshpande, J. Farley, M. Halsey, S. Michalakis, P.-O. Persson, P. Pylyavskyy, L. Rademacher, A. Riehl, M. Rios, J. Samuel, B. Tenner, A. Vijayasaraty, L. Zhao and D. J. Kleitman, Partitioning a planar graph of girth ten into a forest and a matching, manuscript (2004).
- [2] O.V. Borodin, Consistent colorings of graphs on the plane, Diskret. Analiz 45 (1987) 21-27 (in Russian). Zbl0643.05029
- [3] O. Borodin, A. Kostochka, N. Sheikh and G. Yu, Decomposing a planar graph with girth nine into a forest and a matching, European Journal of Combinatorics 29 (2008) 1235-1241, doi: 10.1016/j.ejc.2007.06.020. Zbl1144.05019
- [4] O. Borodin, A. Kostochka, N. Sheikh and G. Yu, M-degrees of quadrangle-free planar graphs, J. Graph Theory 60 (2009) 80-85, doi: 10.1002/jgt.20346. Zbl1161.05024
- [5] W. He, X. Hou, K.W. Lih, J. Shao, W. Wang and X. Zhu, Edge-partitions of planar graphs and their game coloring numbers, J. Graph Theory 41 (2002) 307-317, doi: 10.1002/jgt.10069. Zbl1016.05033
- [6] D.J. Kleitman, Partitioning the edges of a girth 6 planar graph into those of a forest and those of a set of disjoint paths and cycles, manuscript.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.