Towards a conjecture of Birmelé-Bondy-Reed on the Erdős-Pósa property of long cycles. (English) Zbl 1522.05242
Summary: A conjecture of E. Birmelé et al. [Combinatorica 27, No. 2, 135–145 (2007; Zbl 1136.05028)] states that for any integer \(\ell \geq 3\), every graph \(G\) without two vertex-disjoint cycles of length at least \(\ell\) contains a set of at most \(\ell\) vertices which meets all cycles of length at least \(\ell\). They showed the existence of such a set of at most \(2\ell +3\) vertices. This was improved by D. Meierling et al. [J. Graph Theory 77, No. 4, 251–259 (2014; Zbl 1304.05084)] to \(5\ell/3+29/2\). Here we present a proof showing that at most \(3\ell/2+7/2\) vertices suffice.
{© 2022 Wiley Periodicals LLC.}
{© 2022 Wiley Periodicals LLC.}
References:
| [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, Combinatorica.27 (2007), no. 2, 135-145. · Zbl 1136.05028 |
| [3] | H.Bruhn, M.Heinlein, and F.Joos, Long cycles have the edge‐Erdős-Pósa property, Combinatorica. 39 (2019), no. 1, 1-36. · Zbl 07058284 |
| [4] | H.Bruhn, F.Joos, and O.Schaudt, Long cycles through prescribed vertices have the Erdős-Pósa property, J. Graph Theory. 87 (2018), no. 3, 275-284. · Zbl 1386.05095 |
| [5] | W.Cames Van Batenburg, G.Joret, and A.Ulmer, Erdős-Pósa from ball packing, SIAM J. Discrete Math. (2020), no. 3, 1609-1619. · Zbl 1450.05045 |
| [6] | P.Erdős and L.Pósa, On independent circuits contained in a graph, Canad. J. Math. 17 (1965), 347-352. · Zbl 0129.39904 |
| [7] | S.Fiorini and A.Herinckx, A tighter Erdős-Pósa function for long cycles, J. Graph Theory, 77 (2014), no. 2, 111-116. · Zbl 1408.05074 |
| [8] | M.Kang, O.Kwon, and M.Lee, Graphs without two vertex‐disjoint \(S\)‐cycles, Discrete Math. 343 (2020), no. 10, 111997, 18pp. · Zbl 1445.05056 |
| [9] | E.Kim and O.Kwon, Erdős-Pósa property of chordless cycles and its applications, J. Combin. Theory Ser. B. 145 (2020), 65-112. · Zbl 1448.05115 |
| [10] | L.Lovász, On graphs not containing independent circuits (Hungarian), Mat. Lapok. 16 (1965), 289-299. · Zbl 0151.33403 |
| [11] | D.Meierling, D.Rautenbach, and T.Sasse, The Erdős-Pósa property for long circuits, J. Graph Theory. 77 (2014), no. 4, 251-259. · Zbl 1304.05084 |
| [12] | F.Mousset, A.Noever, N.Škorić, and F.Weissenberger, A tight Erdős-Pósa function for long cycles, J. Combin. Theory Ser. B. 125 (2017), 21-32. · Zbl 1362.05106 |
| [13] | J.‐F.Raymond and D. M.Thilikos, Recent techniques and results on the Erdős-Pósa property, Discrete Appl. Math.2313 (2017), 25-43. · Zbl 1369.05177 |
| [14] | D.Weißauer, In absence of long chordless cycles, large tree‐width becomes a local phenomenon, J. Combin. Theory Ser. B. 139 (2019), 342-352. · Zbl 1428.05122 |
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.
