A tight Erdős–Pósa function for wheel minors

Pierre Aboulker; Samuel Fiorini; Tony Huynh; Gwenaël Joret; Jean Florent Raymond; Ignasi Sau

doi:10.1137/17M1153169

A tight Erdős–Pósa function for wheel minors

Pierre Aboulker, Samuel Fiorini, Tony Huynh, Gwenaël Joret, Jean Florent Raymond, Ignasi Sau

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

3 Citations (Scopus)

Abstract

Let Wt denote the wheel on t + 1 vertices. We prove that for every integer t ≥ 3 there is a constant c = c(t) such that for every integer k ≥ 1 and every graph G, either G has k vertex-disjoint subgraphs each containing Wt as a minor, or there is a subset X of at most ck log k vertices such that G - X has no Wt minor. This is best possible, up to the value of c. We conjecture that the result remains true more generally if we replace Wt with any fixed planar graph H.

Original language	English
Pages (from-to)	2302-2312
Number of pages	11
Journal	SIAM Journal on Discrete Mathematics
Volume	32
Issue number	3
DOIs	https://doi.org/10.1137/17M1153169
Publication status	Published - 1 Jan 2018
Externally published	Yes

Keywords

Covering
Erdos--Pósa property
Packing
Wheel minors

Access to Document

10.1137/17M1153169

Cite this

@article{0787340c09fe4d7eb56e9961d65c153a,

title = "A tight Erd{\H o}s–P{\'o}sa function for wheel minors",

abstract = "Let Wt denote the wheel on t + 1 vertices. We prove that for every integer t ≥ 3 there is a constant c = c(t) such that for every integer k ≥ 1 and every graph G, either G has k vertex-disjoint subgraphs each containing Wt as a minor, or there is a subset X of at most ck log k vertices such that G - X has no Wt minor. This is best possible, up to the value of c. We conjecture that the result remains true more generally if we replace Wt with any fixed planar graph H.",

keywords = "Covering, Erdos--P{\'o}sa property, Packing, Wheel minors",

author = "Pierre Aboulker and Samuel Fiorini and Tony Huynh and Gwena{\"e}l Joret and Raymond, {Jean Florent} and Ignasi Sau",

year = "2018",

month = jan,

day = "1",

doi = "10.1137/17M1153169",

language = "English",

volume = "32",

pages = "2302--2312",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial & Applied Mathematics (SIAM)",

number = "3",

}

TY - JOUR

T1 - A tight Erdős–Pósa function for wheel minors

AU - Aboulker, Pierre

AU - Fiorini, Samuel

AU - Huynh, Tony

AU - Joret, Gwenaël

AU - Raymond, Jean Florent

AU - Sau, Ignasi

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Let Wt denote the wheel on t + 1 vertices. We prove that for every integer t ≥ 3 there is a constant c = c(t) such that for every integer k ≥ 1 and every graph G, either G has k vertex-disjoint subgraphs each containing Wt as a minor, or there is a subset X of at most ck log k vertices such that G - X has no Wt minor. This is best possible, up to the value of c. We conjecture that the result remains true more generally if we replace Wt with any fixed planar graph H.

AB - Let Wt denote the wheel on t + 1 vertices. We prove that for every integer t ≥ 3 there is a constant c = c(t) such that for every integer k ≥ 1 and every graph G, either G has k vertex-disjoint subgraphs each containing Wt as a minor, or there is a subset X of at most ck log k vertices such that G - X has no Wt minor. This is best possible, up to the value of c. We conjecture that the result remains true more generally if we replace Wt with any fixed planar graph H.

KW - Covering

KW - Erdos--Pósa property

KW - Packing

KW - Wheel minors

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

U2 - 10.1137/17M1153169

DO - 10.1137/17M1153169

M3 - Article

AN - SCOPUS:85053886557

SN - 0895-4801

VL - 32

SP - 2302

EP - 2312

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -

A tight Erdős–Pósa function for wheel minors

Abstract

Keywords

Access to Document

Other files and links

Cite this