Title: The Erdős–Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces
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.
Publication Year: 2006
Publication Date: 2006-08-25
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 17
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot