Packing and covering balls in graphs excluding a minor

DOI10.1007/S00493-020-4423-3MaRDI QIDQ2043760zbMATH OpenOpenAlexFDO

Authors Nicolas Bousquet, Wouter Cames van Batenburg, L. Esperet, Gwenaël Joret, William Lochet, Carole Muller, François Pirot

Publication date 3 August 2021

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2001.04517

zbMATH Keywords

coveringpacking

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph minors (05C83)

Abstract: We prove that for every integer $tge1$ there exists a constant $c_t$ such that for every $K_t$-minor-free graph $G$, and every set $S$ of balls in $G$, the minimum size of a set of vertices of $G$ intersecting all the balls of $S$ is at most $c_t$ times the maximum number of vertex-disjoint balls in $S$. This was conjectured by Chepoi, Estellon, and Vax`es in 2007 in the special case of planar graphs and of balls having the same radius.

Review text

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.

Recommendations

• Covering nearly surface-embedded graphs with a fixed number of balls
• VC-dimension and Erdős-Pósa property
• A tight Erdős-Pósa function for planar minors
• An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
• Covering planar graphs with a fixed number of balls

Cites work

• -nets and simplex range queries
• An extremal function for contractions of graphs
• Approximate min-max relations for odd cycles in planar graphs
• Approximations and optimal geometric divide-and-conquer
• Bounding the vertex cover number of a hypergraph
• Cliques in graphs excluding a complete graph minor
• Coloring Jordan regions and curves
• Constant-factor approximation of the domination number in sparse graphs
• Covering nearly surface-embedded graphs with a fixed number of balls
• Covering planar graphs with a fixed number of balls
• Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Lower bound of the Hadwiger number of graphs by their average degree
• On Independent Circuits Contained in a Graph
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Packing and covering with balls on Busemann surfaces
• Packing directed circuits
• Planar diameter via metric compression
• Problems from CGCS Luminy, May 2007
• Quasi-planar graphs have a linear number of edges
• Strongly sublinear separators and polynomial expansion
• The Gallai-Younger conjecture for planar graphs
• The intrinsic dimensionality of graphs
• VC-dimension and Erdős-Pósa property

Cited in

(5)

• VC-dimension and Erdős-Pósa property
• Packing minor closed families of graphs
• On covering bridged plane triangulations with balls
• Twin-width. III: Max independent set, min dominating set, and coloring
• Covering nearly surface-embedded graphs with a fixed number of balls

This page was built for publication: Packing and covering balls in graphs excluding a minor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2043760)