Erdős–Pósa conjecture for long cycles through prescribed vertices
Erdős–Pósa conjecture for long cycles through prescribed vertices
Let be a graph, let , and let be positive integers. An -cycle is a cycle containing a vertex of .
Long -cycle Erdős–Pósa conjecture. For every graph , every subset of vertices , and every pair of positive integers , there is either a set of disjoint -cycles of length at least , or a set with
such that contains no -cycle of length at least .
This conjecture improves the known bound of order for the corresponding hitting set when both parameters vary. The examples discussed in the source show that the dependence on and on cannot generally be reduced when the other parameter is fixed, while the optimal bound when both grow remains open.
Sources & referencesView supporting material
Primary source
Henning Bruhn, Felix Joos and Oliver Schaudt, “Long cycles through prescribed vertices have the Erdős-Pósa property”, arXiv:1412.2894 (2015).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.