Portal de Periódicos da CAPES

Decomposing a planar graph with girth 9 into a forest and a matching

2007; Elsevier BV; Volume: 29; Issue: 5 Linguagem: Inglês

10.1016/j.ejc.2007.06.020

1095-9971

O. V. Borodin, Alexandr Kostochka, Naeem N. Sheikh, Gexin Yu,

Graph Labeling and Dimension Problems

W. He et al. showed that a planar graph of girth 11 can be decomposed into a forest and a matching. D. Kleitman et al. proved the same statement for planar graphs of girth 10. We further improve the bound on girth to 9.