, has small maximum degree, a small edge-hitting set can be constructed from a small vertex-hitting set. On the other hand, a big maximum degree forces a large packing of ? r -models

If f r is the vertex-Erd? os-Pósa gap of M(? r ), then the edge-Erd? os-Pósa gap of M(? r ) is less than 2kr · f r (k) ,

, be an integer and let f r is the vertex-Erd? os-Pósa gap of M(? r ) We want to prove that if G contains less than k edge-disjoint models of ? r , then it has a ? r -edge-hitting set of size less than 2kr · f r (k) According to Remark 1, we can assume that G is biconnected. If it is not the case, we consider its biconnected components separately (if it has no biconnected component then the lemma is trivial)

Notice that if G does not contain k edge-disjoint ? r -models, it does not contain k vertexdisjoint ? r -models either. Consequently, there is a set X ? V(G) meeting every ? r model of G and such that |X| f r (k) Let us consider the set Y ? E(G) of edges incident to vertices of X, i.e. Y = {{u, v} ? E(G), u ? X}. Remark that as ?(G) < 2kr, we have |Y | 2kr · f r (k). Now, assume that there is a ? r -model in G not having edges in Y. None of its vertices is in X, which is contradictory ,

, Corollary 2. An edge-gap of O(k 3 r 3 ) for M(? r ) can be derived from Proposition

, Proof of Theorem 1. It follows from the application of Lemma 7 to the estimations of the vertex-Erd? os-Pósa gap of ? r given in Corollary 1

, The main question is whether for every planar graph J, the class M(J) satisfies this edge variant of the Erd? os-Pósa property. As for the vertex version, it is easy to see that the planarity of J is necessary. For instance, if J = K 5 , consider as graph G an n-vertex toroidal wall, which is a 3-regular graph embeddable in the torus that contains K 5 as a minor. One can check that G does not contain two edge-disjoint models of K 5

does it hold with a polynomial gap for all graphs? Also, finding lower bounds on this gap for specific graphs is another interesting and complementary question Let us mention that, as it is the case for the vertex version (see [5, 8]), for any non-acyclic planar graph J for which the edge variant References [1] E. Birmelé, J. Bondy, and B. Reed. Brambles, prisms and grids, Graph Theory in Paris, Trends in Mathematics, pp.37-44, 2007. ,

Large-treewidth graph decompositions and applications, Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, STOC '13, pp.291-300, 2013. ,

DOI : 10.1145/2488608.2488645

Polynomial bounds for the grid-minor theorem. CoRR, abs/1305, 2013. ,

Graph Theory, volume 173 of Graduate Texts in Mathematics, 2005. ,

On independent circuits contained in a graph, Journal canadien de math??matiques, vol.17, issue.0, pp.347-352, 1965. ,

DOI : 10.4153/CJM-1965-035-8

, , 2013.

Optimal Erd? os?Pósa property for pumpkins, 2013. ,

Excluded Forest Minors and the Erd??s???P??sa Property, Combinatorics, Probability and Computing, vol.22, issue.05, pp.700-721, 2013. ,

DOI : 10.1007/978-3-642-23719-5

Quadratic upper bounds on the Erd? os?Pósa property for a generalization of packing and covering cycles, Journal of Graph Theory, 2013. ,

Strengthening Erd??s-P??sa property for minor-closed graph classes, Journal of Graph Theory, vol.21, issue.2, pp.235-240, 2011. ,

DOI : 10.1007/s004930100028

Hitting and Harvesting Pumpkins, Algorithms ? ESA 2011, pp.394-407, 2011. ,

DOI : 10.1006/jctb.1995.1006

URL : https://hal.archives-ouvertes.fr/lirmm-00642341

Edge-disjoint odd cycles in 4-edge-connected graphs, 29th International Symposium on Theoretical Aspects of Computer Science (STACS), pp.206-217, 2012. ,

DOI : 10.1016/j.jctb.2015.12.002

URL : https://hal.archives-ouvertes.fr/hal-00678188

, Treewidth. Computations and Approximations LNCS, vol.842, 1994.

Treewidth and planar minors, 2012. ,

Low polynomial exclusion of planar graph patterns. CoRR, abs/1305, 2013. ,

URL : https://hal.archives-ouvertes.fr/lirmm-01263767

Polynomial Gap Extensions of the Erd? os?Pósa Theorem, 7th European Conference on Combinatorics, Graph Theory and Applications (EuroComb), 2013. ,

Polynomial treewidth forces a large grid-like-minor, European Journal of Combinatorics, vol.33, issue.3, pp.374-379, 2012. ,

DOI : 10.1016/j.ejc.2011.09.004

Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory, Series B, vol.41, issue.1, pp.92-114, 1986. ,

DOI : 10.1016/0095-8956(86)90030-4