Premium
The Erdős–Pósa Property for Long Circuits
Author(s) -
Meierling Dirk,
Rautenbach Dieter,
Sasse Thomas
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21769
Subject(s) - combinatorics , disjoint sets , mathematics , conjecture , electronic circuit , vertex (graph theory) , discrete mathematics , integer (computer science) , property (philosophy) , graph , upper and lower bounds , set (abstract data type) , computer science , physics , mathematical analysis , philosophy , epistemology , programming language , quantum mechanics
For an integer ℓ at least 3, we prove that if G is a graph containing no two vertex‐disjoint circuits of length at least ℓ, then there is a set X of at most5 3 ℓ + 29 2vertices that intersects all circuits of length at least ℓ. Our result improves the bound 2 ℓ + 3 due to Birmelé, Bondy, and Reed (The Erdős–Pósa property for long circuits, Combinatorica 27 (2007), 135–145) who conjecture that ℓ vertices always suffice.