Packing and covering balls in graphs excluding a minor (Q2043760)

The paper under review considers graphs with no \(K_{t}\)-minor. The main result proved is that given \(t\geq 1\), there is a constant \(c_{t}\) such that for any \(K_{t}\)-free graph \(G\) and every set of balls in \(G\), the minimum size of a set of vertices intersecting all the balls is at most \(c_{t}\) times the size of a largest collection of disjoint balls. Here as usual the ball of radius \(r\) centred at a vertex \(v\) in a graph is the set of all vertices at graph distance at most \(r\) from \(v\) in the graph. In the language of hypergraph theory, this states that the transversal number of the hypergraph \(\mathcal{H}\) with vertex set \(V(G)\) and hyperedges the set \(S\) of balls has transversal number (smallest size of a set of vertices intersecting all edges), \(\tau(\mathcal{H})\) at most \(c_{t}\) times the matching number \(\mu(\mathcal{H})\). (Note that the inequality \(\tau(\mathcal{H})\geq \nu(\mathcal{H})\) is immediate). It is important to understand that \(c_{t}\) does not depend on the radii of the balls. Of course the result applies in particular to planar graphs as planarity implies no \(K_{5}\)-minor. The proofs use the Erdős-Pósa property of the ball hypergraphs and results on their Vapnik-Chervonenkis dimension. The proof of the main result is constructive and could be turned into an efficient algorithm to find a transversal.