## $$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.

### MSC:

 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: