首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号