Packing and covering balls in graphs excluding a minor

DOI10.1007/s00493-020-4423-3zbMath1488.05468arXiv2001.04517OpenAlexW2999194922MaRDI QIDQ2043760

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

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

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

Cites Work

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

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