Decompositions of quadrangle-free planar graphs

• Autorzy: Oleg V. Borodin , Anna O. Ivanova , Alexandr V. Kostochka , Naeem N. Sheikh
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

planar graphs; graph decompositions; quadrangle-free graphs

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C35: Extremal problems
• 05C10: Planar graphs; geometric and topological aspects of graph theory

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2009
• Tom: 29
• Numer: 1
• Strony: 87-99

Daty

wydano

2009

otrzymano

2007-11-27

poprawiono

2008-08-01

zaakceptowano

2008-08-29

Twórcy

autor

Oleg V. Borodin

• Sobolev Institute of Mathematics, Novosibirsk 630090, Russia

autor

Anna O. Ivanova

• Yakutsk State University, Yakutsk, 677000, Russia

autor

Alexandr V. Kostochka

• Department of Mathematics, University of Illinois, Urbana, IL 61801, USA
• Sobolev Institute of Mathematics, Novosibirsk 630090, Russia

autor

Naeem N. Sheikh

• Department of Mathematics, University of Illinois, Urbana, IL 61801, USA

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1434