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

At least 4 years old · documented by

For each ℓ≥3\ell\geq 3, let CℓC_\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 k∈Nk\in\mathbb{N}. Long-hole Erdős–Pósa conjecture. There exists a function f(k)=O(klog⁡k)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 G−XG-X has no hole of length at least 66. The paper proves the weaker O(k2log⁡k)\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.

References

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).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.