Quadratic Upper Bounds on the Erdős–Pósa Property for a Generalization of Packing and Covering Cycles |
| |
Authors: | Fedor V. Fomin Daniel Lokshtanov Neeldhara Misra Geevarghese Philip Saket Saurabh |
| |
Affiliation: | 1. DEPARTMENT OF INFORMATICS, UNIVERSITY OF BERGEN, , N‐5020 BERGEN, NORWAY;2. UNIVERSITY OF CALIFORNIA, , LA JOLLA, CA, 92093‐0404;3. THE INSTITUTE OF MATHEMATICAL SCIENCES, , CHENNAI, 600113 INDIA |
| |
Abstract: | According to the classical Erd?s–Pósa theorem, given a positive integer k, every graph G either contains k vertex disjoint cycles or a set of at most vertices that hits all its cycles. Robertson and Seymour (J Comb Theory Ser B 41 (1986), 92–114) generalized this result in the best possible way. More specifically, they showed that if is the class of all graphs that can be contracted to a fixed planar graph H, then every graph G either contains a set of k vertex‐disjoint subgraphs of G, such that each of these subgraphs is isomorphic to some graph in or there exists a set S of at most vertices such that contains no subgraph isomorphic to any graph in . However, the function f is exponential. In this note, we prove that this function becomes quadratic when consists all graphs that can be contracted to a fixed planar graph . For a fixed c, is the graph with two vertices and parallel edges. Observe that for this corresponds to the classical Erd?s–Pósa theorem. |
| |
Keywords: | Erdos Posa property generalization of covering and packing cycles |
|
|