The Erdős–Pósa Property for Long Circuits | Zendy

Meierling Dirk | Zendy; Rautenbach Dieter | Zendy; Sasse Thomas | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research