Chepoi–Estellon–Vaxès linear Erdős–Pósa conjecture for planar ball hypergraphs

Let GG be a planar graph and let u(G) u_{\ell}(G) and τ(G)\tau_{\ell}(G) denote, respectively, the packing number and transversality of its hypergraph of balls of radius \ell. Chepoi–Estellon–Vaxès' conjecture. There \exists a constant cc such that, for every \ell and every planar graph GG,

τ(G)cν(G).\tau_{\ell}(G) \leq c \cdot \nu_{\ell}(G).

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 \ell, 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

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.