The Erdős–Pósa property for edge-disjoint immersions in 4-edge-connected graphs

Naonori Kakimura; Ken ichi Kawarabayashi

doi:10.1016/j.jctb.2018.02.003

The Erdős–Pósa property for edge-disjoint immersions in 4-edge-connected graphs

Naonori Kakimura, Ken ichi Kawarabayashi

Department of Mathematics

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

2 Citations (Scopus)

Abstract

A graph H is immersed in a graph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. In this paper, we show that the Erdős–Pósa property holds for packing edge-disjoint K_t-immersions in 4-edge-connected graphs. More precisely, for positive integers k and t, there exists a constant f(k,t) such that a 4-edge-connected graph G has either k edge-disjoint K_t-immersions, or an edge subset F of size at most f(k,t) such that G−F has no K_t-immersion. The 4-edge-connectivity in this statement is best possible in the sense that 3-edge-connected graphs do not have the Erdős–Pósa property.

Original language	English
Pages (from-to)	138-169
Number of pages	32
Journal	Journal of Combinatorial Theory. Series B
Volume	131
DOIs	https://doi.org/10.1016/j.jctb.2018.02.003
Publication status	Published - 2018 Jul

Keywords

4-Edge-connected graphs
Covering
Immersion
Packing

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jctb.2018.02.003

Cite this

@article{2babd72d909d4ec9b045d93ba0345639,

title = "The Erd{\H o}s–P{\'o}sa property for edge-disjoint immersions in 4-edge-connected graphs",

abstract = "A graph H is immersed in a graph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. In this paper, we show that the Erd{\H o}s–P{\'o}sa property holds for packing edge-disjoint Kt-immersions in 4-edge-connected graphs. More precisely, for positive integers k and t, there exists a constant f(k,t) such that a 4-edge-connected graph G has either k edge-disjoint Kt-immersions, or an edge subset F of size at most f(k,t) such that G−F has no Kt-immersion. The 4-edge-connectivity in this statement is best possible in the sense that 3-edge-connected graphs do not have the Erd{\H o}s–P{\'o}sa property.",

keywords = "4-Edge-connected graphs, Covering, Immersion, Packing",

author = "Naonori Kakimura and Kawarabayashi, {Ken ichi}",

note = "Funding Information: Supported by JST ERATO Grant Number JPMJER1201. Publisher Copyright: {\textcopyright} 2018 Elsevier Inc.",

year = "2018",

month = jul,

doi = "10.1016/j.jctb.2018.02.003",

language = "English",

volume = "131",

pages = "138--169",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - The Erdős–Pósa property for edge-disjoint immersions in 4-edge-connected graphs

AU - Kakimura, Naonori

AU - Kawarabayashi, Ken ichi

PY - 2018/7

Y1 - 2018/7

N2 - A graph H is immersed in a graph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. In this paper, we show that the Erdős–Pósa property holds for packing edge-disjoint Kt-immersions in 4-edge-connected graphs. More precisely, for positive integers k and t, there exists a constant f(k,t) such that a 4-edge-connected graph G has either k edge-disjoint Kt-immersions, or an edge subset F of size at most f(k,t) such that G−F has no Kt-immersion. The 4-edge-connectivity in this statement is best possible in the sense that 3-edge-connected graphs do not have the Erdős–Pósa property.

AB - A graph H is immersed in a graph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. In this paper, we show that the Erdős–Pósa property holds for packing edge-disjoint Kt-immersions in 4-edge-connected graphs. More precisely, for positive integers k and t, there exists a constant f(k,t) such that a 4-edge-connected graph G has either k edge-disjoint Kt-immersions, or an edge subset F of size at most f(k,t) such that G−F has no Kt-immersion. The 4-edge-connectivity in this statement is best possible in the sense that 3-edge-connected graphs do not have the Erdős–Pósa property.

KW - 4-Edge-connected graphs

KW - Covering

KW - Immersion

KW - Packing

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

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

U2 - 10.1016/j.jctb.2018.02.003

DO - 10.1016/j.jctb.2018.02.003

M3 - Article

AN - SCOPUS:85042390871

SN - 0095-8956

VL - 131

SP - 138

EP - 169

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

The Erdős–Pósa property for edge-disjoint immersions in 4-edge-connected graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this