An edge variant of the Erdos-Pósa property

Jean Florent Raymond; Ignasi Sau; Dimitrios M. Thilikos

doi:10.1016/j.disc.2016.03.004

An edge variant of the Erdos-Pósa property

Jean Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

For every r ϵ ℕ, we denote by θ_r the multigraph with two vertices and r parallel edges. Given a graph G, we say that a subgraph H of G is a model of θ_r in G if H contains θ_r as a contraction. We prove that the following edge variant of the Erdos-Pósa property holds for every ≥ 2: if G is a graph and k is a positive integer, then either G contains a packing of k mutually edge-disjoint models of θ_r, or it contains a set S of f_r(k) edges such that G\S has no θ_r-model, for both f_r(k) = O(k²r³polylog kr) and f_r(k)=O(k⁴r²polylog kr).

Original language	English (US)
Pages (from-to)	2027-2035
Number of pages	9
Journal	Discrete Mathematics
Volume	339
Issue number	8
DOIs	https://doi.org/10.1016/j.disc.2016.03.004
State	Published - Aug 6 2016

Keywords

Coverings in graphs
Erdos-Pósa property
Packings in graphs

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2016.03.004

Cite this

@article{0beb00b3a67140d1b3faffc47768c3f9,

title = "An edge variant of the Erdos-P{\'o}sa property",

abstract = "For every r ϵ ℕ, we denote by θr the multigraph with two vertices and r parallel edges. Given a graph G, we say that a subgraph H of G is a model of θr in G if H contains θr as a contraction. We prove that the following edge variant of the Erdos-P{\'o}sa property holds for every ≥ 2: if G is a graph and k is a positive integer, then either G contains a packing of k mutually edge-disjoint models of θr, or it contains a set S of fr(k) edges such that G\S has no θr-model, for both fr(k) = O(k2r3polylog kr) and fr(k)=O(k4r2polylog kr).",

keywords = "Coverings in graphs, Erdos-P{\'o}sa property, Packings in graphs",

author = "Raymond, {Jean Florent} and Ignasi Sau and Thilikos, {Dimitrios M.}",

year = "2016",

month = aug,

day = "6",

doi = "10.1016/j.disc.2016.03.004",

language = "English (US)",

volume = "339",

pages = "2027--2035",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "8",

}

TY - JOUR

T1 - An edge variant of the Erdos-Pósa property

AU - Raymond, Jean Florent

AU - Sau, Ignasi

AU - Thilikos, Dimitrios M.

PY - 2016/8/6

Y1 - 2016/8/6

N2 - For every r ϵ ℕ, we denote by θr the multigraph with two vertices and r parallel edges. Given a graph G, we say that a subgraph H of G is a model of θr in G if H contains θr as a contraction. We prove that the following edge variant of the Erdos-Pósa property holds for every ≥ 2: if G is a graph and k is a positive integer, then either G contains a packing of k mutually edge-disjoint models of θr, or it contains a set S of fr(k) edges such that G\S has no θr-model, for both fr(k) = O(k2r3polylog kr) and fr(k)=O(k4r2polylog kr).

AB - For every r ϵ ℕ, we denote by θr the multigraph with two vertices and r parallel edges. Given a graph G, we say that a subgraph H of G is a model of θr in G if H contains θr as a contraction. We prove that the following edge variant of the Erdos-Pósa property holds for every ≥ 2: if G is a graph and k is a positive integer, then either G contains a packing of k mutually edge-disjoint models of θr, or it contains a set S of fr(k) edges such that G\S has no θr-model, for both fr(k) = O(k2r3polylog kr) and fr(k)=O(k4r2polylog kr).

KW - Coverings in graphs

KW - Erdos-Pósa property

KW - Packings in graphs

UR - http://www.scopus.com/inward/record.url?scp=84964661082&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84964661082&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2016.03.004

DO - 10.1016/j.disc.2016.03.004

M3 - Article

AN - SCOPUS:84964661082

SN - 0012-365X

VL - 339

SP - 2027

EP - 2035

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 8

ER -

An edge variant of the Erdos-Pósa property

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this