Properly Colored Geometric Matchings and 3-Trees Without Crossings on Multicolored Points in the Plane - Discrete and Computational Geometry and Graphs - page 97

graph on is a 2-colored

point set. For alternating geometric perfect matchings on a 2-colored point set,
the next theorem is well-known.

X , which is also called an alternating geometric graph if X

Theorem 1.1 ( [ 5 ] ). Let be sets of red and blue points in the plane,

respectively. Assume that no three points of

R and B

R ∪ B are collinear. If |R| = |B| ,

then there exists a non-crossing alternating geometric perfect matching on R∪B .

In this paper, we first generalize this Theorem 1.1 for a 3-colored point set, stated
as Theorem 1.2 (Fig. 1 ). Note that Theorem 1.1 is a special case of Theorem 1.2
with

G = ∅ .

Theorem 1.2. Let be sets of red, blue, and green points in the plane,

respectively. Assume that no three points of

R , B , G

X = R ∪ B ∪ G are collinear. If

|X| |X|/

2 points, then there exists a
non-crossing properly colored geometric perfect matching on

is even and each color appears on at most

X

.

Fig. 1. A non-crossing properly colored geometric perfect matching (Color figure

online).

Next, we consider a tree of maximum degree at most 3, which is called a 3-tree .
Kaneko [ 2 ] proved the following theorem.

Theorem 1.3 (Kaneko [ 2 ] ). Let be sets of red and blue points in

the plane, respectively. Assume that no three points of

R and B

R ∪ B are collinear. If

|R| |B|

= , then there exists a non-crossing alternating geometric spanning 3 -tree

R ∪ B

on .

Our second result is a generalization of this Theorem 1.3 for a 3-colored point
set, stated as Theorem 1.4 (Fig. 2 ).

Theorem 1.4. Let be sets of red, blue, and green points in the plane,

respectively. Assume that no three points of

R , B , G

X = R ∪ B ∪ G are collinear. If

each color appears on at most points, then there exists a non-crossing

properly colored geometric spanning 3 -tree on

|X|/ 2

X .

If is even, then we can obtain this Theorem 1.4 as a corollary from our

Theorem 1.2 and the following theorem by Hoffmann and Toth [ 1 ].

|X|

Theorem 1.5 (Hoffmann and Toth [ 1 ] ). Every disconnected properly colored
geometric graph with no isolated vertices can be augmented (by adding edges) into
a connected properly colored geometric graph so that the degree of every vertex
increases by at most two.