Canadian Mathematical Society www.cms.math.ca
Abstract view

# Indecomposable Coverings

Published:2009-09-01
Printed: Sep 2009
• János Pach
• Gábor Tardos
• Géza Tóth
Features coming soon:
Citations   (via CrossRef) Tools: Search Google Scholar:
 Format: HTML LaTeX MathJax PDF PostScript

## Abstract

We prove that for every $k>1$, there exist $k$-fold coverings of the plane (i) with strips, (ii) with axis-parallel rectangles, and (iii) with homothets of any fixed concave quadrilateral, that cannot be decomposed into two coverings. We also construct for every $k>1$ a set of points $P$ and a family of disks $\cal D$ in the plane, each containing at least $k$ elements of $P$, such that, no matter how we color the points of $P$ with two colors, there exists a disk $D\in{\cal D}$ all of whose points are of the same color.
 MSC Classifications: 52C15 - Packing and covering in $2$ dimensions [See also 05B40, 11H31] 05C15 - Coloring of graphs and hypergraphs

© Canadian Mathematical Society, 2013 : http://www.cms.math.ca/