Discussiones Mathematicae Graph Theory 29(1) (2009)
87-99
DOI: https://doi.org/10.7151/dmgt.1434
DECOMPOSITIONS OF QUADRANGLE-FREE PLANAR GRAPHS
Oleg V. Borodin
Sobolev Institute of Mathematics |
Anna O. Ivanova
Yakutsk State University e-mail: shmgnanna@mail.ru |
Alexandr V. Kostochka
Department of Mathematics |
Naeem N. Sheikh
Department of Mathematics e-mail: nsheikh@math.uiuc.edu |
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.Keywords and phrases: planar graphs, graph decompositions, quadrangle-free graphs.
2000 Mathematics Subject Classification: 05C15, 05C10, 05C35.
References
[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). |
[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. |
[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. |
[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. |
[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. |
Received 27 November 2007
Revised 1 August 2008
Accepted 29 August 2008
Close