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

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Hypergraphs (05C65) 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.

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

• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• 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
• 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
• -nets and simplex range queries

Cited in

(5)

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

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)