Frames, $A$-Paths, and the Erdös--Pósa Property
Authors:
- Henning BruhnHBHenning Bruhn
- Matthias HeinleinMHMatthias Heinlein
- Felix JoosFJFelix Joos
- 1 January 2018
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 32 (2) , 1246-1260
Abstract
A key feature of Simonovits' proof of the classic Erdös--Pósa theorem is a simple subgraph of the host graph, a frame, that determines the outcome of the theorem. We transfer this frame technique to $A$-paths. With it we deduce a simple proof of Gallai's theorem, although with a worse bound, and we verify the Erdös--Pósa property for long and for even $A$-paths. We also show that even $A$-paths do not have the edge-Erdös--Pósa property.Keywords
All Related Versions
Funding Information
- Deutsche Forschungsgemeinschaft (BR 5449/1-1)
- Engineering and Physical Sciences Research Council (EP/M009408/1)
This publication has 25 references indexed in Scilit:
- Packing cycles through prescribed verticesJournal of Combinatorial Theory, Series B, 2011
- Packing cycles with modularity constraintsCombinatorica, 2011
- Packing non-zero A-paths in an undirected model of group labeled graphsJournal of Combinatorial Theory, Series B, 2010
- The Erdős–Pósa Property For Long CircuitsCombinatorica, 2007
- Packing Non-Zero A-Paths In Group-Labelled GraphsCombinatorica, 2006
- A Short Proof of Mader's S-Paths TheoremJournal of Combinatorial Theory, Series B, 2001
- Packing directed circuitsCombinatorica, 1996
- On the presence of disjoint subgraphs of a specified typeJournal of Graph Theory, 1988
- A new proof and generalizations of a theorem of Erdős and Pósa on graphs withoutk+1 independent circuitsActa Mathematica Hungarica, 1967
- On Independent Circuits Contained in a GraphCanadian Journal of Mathematics, 1965