Portal de Periódicos da CAPES

Planar graphs decomposable into a forest and a matching

2008; Elsevier BV; Volume: 309; Issue: 1 Linguagem: Inglês

10.1016/j.disc.2007.12.104

1872-681X

O. V. Borodin, A. O. Ivanova, Alexandr Kostochka, Naeem N. Sheikh,

Limits and Structures in Graph Theory

He, Hou, Lih, Shao, Wang, and Zhu showed that a planar graph of girth 11 can be decomposed into a forest and a matching. Borodin, Kostochka, Sheikh, and Yu improved the bound on girth to 9. We give sufficient conditions for a planar graph with 3-cycles to be decomposable into a forest and a matching.