The Erdös-Pósa property for long circuits. (English) Zbl 1304.05084
From the authors’ abstract: For an integer \(l\) at least 3, we prove that if \(G\) is a graph containing no two vertex-disjoint circuits of length at least 3, then there is a set \(X\) of at most \(5/3 l + 14,5\) vertices that intersects all circuits of length at least \(l\).
This result improves the bound \(2l+3\) due to E. Birmelé et al. [Combinatorica 27, No. 2, 135–145 (2007; Zbl 1136.05028)] who conjectured that \(l\) vertices always suffice.
This result improves the bound \(2l+3\) due to E. Birmelé et al. [Combinatorica 27, No. 2, 135–145 (2007; Zbl 1136.05028)] who conjectured that \(l\) vertices always suffice.
Reviewer: Michael Hager (Leonberg)
MSC:
| 05C38 | Paths and cycles |
| 05C35 | Extremal problems in graph theory |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
Citations:
Zbl 1136.05028References:
| [1] | E.Birmelé, Thèse de doctorat, Université de Lyon 1, 2003. |
| [2] | E.Birmelé, J. A.Bondy, and B. A.Reed, The Erdős‐Pósa property for long circuits, Combinatorica27 (2007), 135-145. · Zbl 1136.05028 |
| [3] | P.Erdős and L.Pósa, On independent circuits contained in a graph, Canad J Math17 (1965), 347-352. · Zbl 0129.39904 |
| [4] | S.Fiorini and A.Herinckx, A tighter Erdos‐Posa function for long cycles, J Graph Theory. · Zbl 1408.05074 |
| [5] | L.Lovász, On graphs not containing independent circuits (Hungarian), Mat Lapok16 (1965), 289-299. · Zbl 0151.33403 |
| [6] | C.Thomassen, On the presence of disjoint subgraphs of a specified type, J Graph Theory12 (1988), 101-111. · Zbl 0662.05032 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
