CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  PublicationsjournalsCMB
Publications        
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, 05C15 show english descriptions Packing and covering in $2$ dimensions [See also 05B40, 11H31]
Coloring of graphs and hypergraphs
52C15 - Packing and covering in $2$ dimensions [See also 05B40, 11H31]
05C15 - Coloring of graphs and hypergraphs
 

© Canadian Mathematical Society, 2014 : https://cms.math.ca/