{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T01:12:13Z","timestamp":1773882733164,"version":"3.50.1"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","issue":"Combinatorics","license":[{"start":{"date-parts":[[2019,1,31]],"date-time":"2019-01-31T00:00:00Z","timestamp":1548892800000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"},{"start":{"date-parts":[[2019,1,31]],"date-time":"2019-01-31T00:00:00Z","timestamp":1548892800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"},{"start":{"date-parts":[[2019,1,31]],"date-time":"2019-01-31T00:00:00Z","timestamp":1548892800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"crossref","award":["734922"],"award-info":[{"award-number":["734922"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["1400653"],"award-info":[{"award-number":["1400653"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>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{8}{9}(r+b-8)$ points of $R\\cup B$ can be $K_{1,3}$-covered. For $r&amp;gt;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.<\/jats:p><jats:p>Comment: 29 pages, 10 figures, 1 table<\/jats:p>","DOI":"10.23638\/dmtcs-21-3-6","type":"journal-article","created":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T16:52:01Z","timestamp":1743699121000},"source":"Crossref","is-referenced-by-count":1,"title":["$K_{1,3}$-covering red and blue points in the plane"],"prefix":"10.23638","volume":"Vol. 21 no. 3","author":[{"given":"Bernardo M.","family":"\u00c1brego","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Silvia","family":"Fern\u00e1ndez-Merchant","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikio","family":"Kano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Orden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pablo","family":"P\u00e9rez-Lantero","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlos","family":"Seara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Javier","family":"Tejel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2019,1,31]]},"container-title":["Discrete Mathematics &amp; Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/arxiv.org\/pdf\/1707.06856v3","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/arxiv.org\/pdf\/1707.06856v3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T16:52:02Z","timestamp":1743699122000},"score":1,"resource":{"primary":{"URL":"http:\/\/dmtcs.episciences.org\/4537"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,31]]},"references-count":0,"journal-issue":{"issue":"Combinatorics","published-online":{"date-parts":[[2019,1,31]]}},"URL":"https:\/\/doi.org\/10.23638\/dmtcs-21-3-6","relation":{"has-preprint":[{"id-type":"arxiv","id":"1707.06856v2","asserted-by":"subject"},{"id-type":"arxiv","id":"1707.06856v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1707.06856","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1707.06856","asserted-by":"subject"}]},"ISSN":["1365-8050"],"issn-type":[{"value":"1365-8050","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,31]]},"article-number":"4537"}}