Packing and covering balls in graphs excluding a minor

DOI10.1007/S00493-020-4423-3zbMATH Open1488.05468arXiv2001.04517OpenAlexW2999194922MaRDI QIDQ2043760FDOQ2043760

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

Publication date: 3 August 2021

Published in: Combinatorica (Search for Journal in Brave)

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.

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)

Cites Work

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

Cited In (2)

• Packing minor closed families of graphs
• 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)