The Erdős–Pósa conjecture for long holes in -free graphs
The Erdős–Pósa conjecture for long holes in -free graphs
For each , let be the cycle of length . A hole is an induced cycle of length at least , and a graph is -free if it contains no . Let . Long-hole Erdős–Pósa conjecture. There exists a function such that for every -free graph , either contains vertex-disjoint holes of length at least , or there is a set of at most vertices such that has no hole of length at least . The paper proves the weaker bound and identifies this sharper bound as an open problem; its broader final open problem concerns other graph classes with the induced Erdős–Pósa property.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Tony Huynh and O-joung Kwon, “On the Erdős-Pósa property for long holes in C_4-free graphs”, arXiv:2105.11799 (2021).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.