Decomposing a planar graph with girth at least 8 into a forest and a matching |
| |
Authors: | Yingqian Wang Qijun Zhang |
| |
Institution: | College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua, 321004, China |
| |
Abstract: | W. He et al. showed that a planar graph of girth at least 11 can be decomposed into a forest and a matching. A. Bass et al. proved the same statement for planar graphs of girth at least 10. Recently, O.V. Borodin et al. improved the bound on the girth to 9. In this paper, we further improve the bound on the girth to 8. This bound is the best possible in the sense that there are planar graphs with girth 7 that cannot be decomposed into a forest and a matching. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|