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


The Erd?s-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces
Authors:Ken-Ichi Kawarabayashi
Institution:a National Institute of Informatics, 2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
b Department of Mathematics, Faculty of Education and Human Sciences, Yokohama National University, 79-2 Tokiwadai, Hodogaya-ku, Yokohama 240-8501, Japan
Abstract:We prove that for any orientable surface S and any non-negative integer k, there exists an integer fS(k) such that every graph G embeddable in S has either k vertex-disjoint odd cycles or a vertex set A of cardinality at most fS(k) such that G-A is bipartite. Such a property is called the Erd?s-Pósa property for odd cycles. We also show its edge version. As Reed Mangoes and blueberries, Combinatorica 19 (1999) 267-296] pointed out, the Erd?s-Pósa property for odd cycles do not hold for all non-orientable surfaces.
Keywords:Erd?s-Pó  sa property  Odd cycles  Orientable surfaces
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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