The O(klogk)\mathcal{O}(k\log k) Erdős–Pósa conjecture for long holes in C4C_4-free graphs

From papers

For each 3\ell\geq 3, let CC_\ell be the cycle of length \ell. A hole is an induced cycle of length at least 44, and a graph is C4C_4-free if it contains no C4C_4. Let kNk\in\mathbb{N}. Long-hole Erdős–Pósa conjecture. There exists a function f(k)=O(klogk)f(k)=\mathcal{O}(k\log k) such that for every C4C_4-free graph GG, either GG contains kk vertex-disjoint holes of length at least 66, or there is a set XX of at most f(k)f(k) vertices such that GXG-X has no hole of length at least 66. The paper proves the weaker O(k2logk)\mathcal{O}(k^2\log k) 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

No solutions have been posted yet.