\(K_{1,3}\)-covering red and blue points in the plane. (English) Zbl 1411.05062

Summary: We say that a finite set of red and blue points in the plane in general position can be \(K_{1,3}\)-covered if the set can be partitioned into subsets of size 4, with 3 points of one color and 1 point of the other color, in such a way that, if at each subset the fourth point is connected by straight-line segments to the same-colored points, then the resulting set of all segments has no crossings. We consider the following problem: Given a set \(R\) of \(r\) red points and a set \(B\) of \(b\) blue points in the plane in general position, how many points of \(R\cup B\) can be \(K_{1,3}\)-covered? and we prove the following results:
(1) If \(r=3g+h\) and \(b=3h+g\), for some non-negative integers \(g\) and \(h\), then there are point sets \(R\cup B\), like \(\{1,3\}\)-equitable sets (i.e., \(r=3b\) or \(b=3r)\) and linearly separable sets, that can be \(K_{1,3}\)-covered.
(2) If \(r=3g+h\), \(b=3h+g\) and the points in \(R\cup B\) are in convex position, then at least \(r+b-4\) points can be \(K_{1,3}\)-covered, and this bound is tight.
(3)] There are arbitrarily large point sets \(R\cup B\) in general position, with \(r=b+1\), such that at most \(r+b-5\) points can be \(K_{1,3}\)-covered.
(4) If \(b\le r\le 3b\), then at least \(\frac 89(r+b-8)\) points of \(R\cup B\) can be \(K_{1,3}\)-covered. For \(r>3b\), there are too many red points and at least \(r-3b\) of them will remain uncovered in any \(K_{1,3}\)-covering.
Furthermore, in all the cases we provide efficient algorithms to compute the corresponding coverings.


05C10 Planar graphs; geometric and topological aspects of graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: arXiv Link