Chepoi–Estellon–Vaxès linear Erdős–Pósa conjecture for planar ball hypergraphs
Chepoi–Estellon–Vaxès linear Erdős–Pósa conjecture for planar ball hypergraphs
Let be a planar graph and let and denote, respectively, the packing number and transversality of its hypergraph of balls of radius . Chepoi–Estellon–Vaxès' conjecture. There \exists a constant such that, for every and every planar graph ,
This conjecture asks for a linear gap between the packing and transversal numbers. It is subsumed by the stated result of Dvořák for bounded-expansion classes only with a coefficient depending on , so the planar linear bound remains unresolved in the supplied text.
Sources & referencesView supporting material
Primary source
Nicolas Bousquet and Stéphan Thomassé, “VC-dimension and Erdős-Pósa property”, arXiv:1412.1793 (2014).
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.