Author’s abstract: The following problem was raised by {\it A. Gyárfás} and {\it J. Lehel} [Discrete Math. 55, 167-180 (1985; Zbl 0569.05020)]. Suppose that some rectangles with parallel sides are given in the plane, such that no $k+1$ of them are mutually disjoint. Is there a constant $c$, independent of $k$, for which they can be “covered with $ck$ points”? (A “point cover” is a set of points, which meets all of the rectangles.) Gyárfás and Lehel observed that $k\sp 2$ points are enough to cover the rectangles. {\it J. Beck} [oral communication] improved this upper bound to $ck\log\sp 2k$, and modifying his ideas here we prove $ck\log k$. The original question still remains open. On the other hand, trivial constructions show that $\lfloor(3/2)k\rfloor$ points are necessary. Indeed, if $k=2$, it is easy to find a configuration consisting of five rectangles whose interaction graph is the 5-cycle. For $k=2n$, set $n$ such configurations disjointly, and for $k=2n+1$ add an isolated rectangle. However, we do not know stronger lower bounds.
Reviewer: R.L.Hemminger (Nashville)