Long cycles through prescribed vertices have the Erdős-Pósa property. (English) Zbl 1386.05095
Summary: We prove that for every graph, any vertex subset \(S\), and given integers \(k,\ell\): there are \(k\) disjoint cycles of length at least \(\ell\) that each contain at least one vertex from \(S\), or a vertex set of size \(O(\ell\cdot k\log k)\) that meets all such cycles. This generalizes previous results of S. Fiorini and A. Herinckx [ibid. 77, No. 2, 111–116 (2014; Zbl 1408.05074)] and of M. Pontecorvi and P. Wollan [J. Comb. Theory, Ser. B 102, No. 5, 1134–1141 (2012; Zbl 1252.05097)].
{
}In addition, we describe an algorithm for our main result that runs in \(O(k\log k\cdot s^2\cdot(f(\ell)\cdot n+m)\) time, where \(s\) denotes the cardinality of \(S\).
References:
| [1] | E.Birmelé, J. A.Bondy, and B.Reed, The Erdős‐Pósa property for long circuits, Combinatorica27 (2007), 135-145. · Zbl 1136.05028 |
| [2] | H. L.Bodlaender, On linear time minor tests with depth‐first search, J. Algorithms14 (1993), 1-23. · Zbl 0764.68107 |
| [3] | J. A.Bondy and L.Lovász, Cycles through specified vertices of a graph, Combinatorica1 (1981), 117-140. · Zbl 0492.05049 |
| [4] | H.Bruhn, M.Heinlein, and F.Joos, Long cycles have the edge‐Erdős‐Pósa property, arXiv:1607.01903 (2016). |
| [5] | R.Diestel, Graph Theory (4th edn.). Springer, Heidelberg, 2010. · Zbl 1204.05001 |
| [6] | R.Diestel, K.Kawarabayashi, and P.Wollan, The Erdős‐Pósa property for clique minors in highly connected graphs, J. Combin. Theory Ser. B102 (2012), 454-469. · Zbl 1239.05172 |
| [7] | G. A.Dirac, In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen, Math. Nachr.22 (1960), 61-85. · Zbl 0096.17903 |
| [8] | P.Erdős and L.Pósa, On the maximal number of disjoint circuits of a graph, Publ. Math. Debrecen9 (1962), 3-12. · Zbl 0133.16701 |
| [9] | S.Fiorini and A.Herinckx, A tighter Erdős‐Pósa function for long cycles, J. Graph Theory77 (2013), 111-116. · Zbl 1408.05074 |
| [10] | F.Havet and A. K.Maia, On disjoint directed cycles with prescribed minimum lengths, INRIA Research ReportRR‐8286 (2013). |
| [11] | T.Huynh, F.Joos, and P.Wollan, A unified Erdős‐Pósa theorem for constrained cycles, arXiv:1605.07082 (2016). |
| [12] | F.Joos, Parity linkage and the Erdős‐Pósa property of odd cycles through prescribed vertices in highly connected graphs, to appear in J. Graph Theory. · Zbl 1417.05167 |
| [13] | N.Kakimura and K.Kawarabayashi, Packing directed circuits through prescribed vertices bounded fractionally, SIAM J. Discrete Math.26 (2012), 1121-1133. · Zbl 1256.05190 |
| [14] | N.Kakimura, K.Kawarabayashi, and D.Marx, Packing cycles through prescribed vertices, J. Combin. Theory (Series B)101 (2011), 378-381. · Zbl 1223.05231 |
| [15] | K.Kawarabayashi and P.Wollan, Non‐zero disjoint cycles in highly connected group labelled graphs, J. Combin. Theory (Series B)96 (2006), 296-301. · Zbl 1090.05038 |
| [16] | D.Meierling, D.Rautenbach, and T.Sasse, The Erdős‐Pósa property for long circuits, J. Graph Theory77 (2014), 251-259. · Zbl 1304.05084 |
| [17] | F.Mousset, A.Noever, N.S̆korić, and F.Weissenberger, A tight Erdős‐Pósa function for long cycles, arXiv:1603.07588 (2016). · Zbl 1362.05106 |
| [18] | M.Pontecorvi and P.Wollan, Disjoint cycles intersecting a set of vertices, J. Combin. Theory (Series B)102 (2012), 1134-1141. · Zbl 1252.05097 |
| [19] | D.Rautenbach and B.Reed, The Erdős‐Pósa property for odd cycles in highly connected graphs, Combinatorica21 (2001), 267-278. · Zbl 0981.05066 |
| [20] | B.Reed, N.Robertson, P.Seymour, and R.Thomas, Packing directed circuits, Combinatorica16 (1996), 535-554. · Zbl 0881.05050 |
| [21] | N.Robertson and P.Seymour, Graph minors. V. Excluding a planar graph, J. Combin. Theory (Series B)41 (1986), 92-114. · Zbl 0598.05055 |
| [22] | M.Simonovits, A new proof and generalizations of a theorem of Erdös and Pósa on graphs without \(k + 1\) independent circuits, Acta Math. Acad. Sci. Hungar.18 (1967), 191-206. · Zbl 0155.31804 |
| [23] | C.Thomassen, On the presence of disjoint subgraphs of a specified type, J. Graph Theory12 (1988), 101-111. · Zbl 0662.05032 |
| [24] | C.Thomassen, The Erdős‐Pósa property for odd cycles in graphs of large connectivity, Combinatorica21 (2001), 321-333. · Zbl 0989.05062 |
| [25] | P.Wollan, Packing cycles with modularity constraints, Combinatorica31 (2011), 95-126. · Zbl 1249.05215 |
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.
