Publication:317324

DOI10.1016/j.aim.2016.07.011zbMath1350.52007arXiv1310.6900OpenAlexW2559490119MaRDI QIDQ317324

Dömötör Pálvölgyi, János Pach

Publication date: 30 September 2016

Published in: Advances in Mathematics, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

cover decompositionhypergraph coloringmultiple coveringsphere packing

Mathematics Subject Classification ID

Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Related Items

Sparse hop spanners for unit disk graphs, Polychromatic colorings of unions of geometric hypergraphs, Coloring points with respect to squares, Coloring intersection hypergraphs of pseudo-disks, Unnamed Item, Coloring Hypergraphs Defined by Stabbed Pseudo-Disks and ABAB-Free Hypergraphs, Coloring Delaunay-edges and their generalizations, Proper coloring of geometric hypergraphs, Coloring intersection hypergraphs of pseudo-disks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Disproof of the neighborhood conjecture with implications to SAT
• Octants are cover-decomposable
• Indecomposable coverings with concave polygons
• Decomposition of multiple coverings into more parts
• Optimally decomposing coverings with translates of a convex polygon
• A non-linear lower bound for planar epsilon-nets
• Convex polygons are self-coverable
• Decomposition of multiple coverings into many parts
• On the transversal number and VC-dimension of families of positive homothets of a convex body
• Covering the plane with convex polygons
• \(\epsilon\)-nets and simplex range queries
• Indecomposable coverings with homothetic polygons
• Convex polygons are cover-decomposable
• Octants are cover-decomposable into many coverings
• Multiple coverings of the plane with triangles
• An Abstract Approach to Polychromatic Coloring: Shallow Hitting Sets in ABA-free Hypergraphs and Pseudohalfplanes
• Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles
• Weighted geometric set cover via quasi-uniform sampling
• Making triangles colorful
• Cover-Decomposition and Polychromatic Numbers
• Venn Diagrams and Independent Families of Sets
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Approximating theDomatic Number
• The determinant bound for discrepancy is almost tight
• Improved bounds and algorithms for hypergraph 2-coloring
• Making Octants Colorful and Related Covering Decomposition Problems
• Survey on Decomposition of Multiple Coverings
• Indecomposable Coverings