×

Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane. (English) Zbl 1452.05064

Akiyama, Jin (ed.) et al., Discrete and computational geometry and graphs. 16th Japanese conference, JCDCGG 2013, Tokyo, Japan, September 17–19, 2013. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 8845, 96-111 (2014).
Summary: Let \(X\) be a set of multicolored points in the plane such that no three points are collinear and each color appears on at most \(\lceil |X|/2 \rceil \) points. We show the existence of a non-crossing properly colored geometric perfect matching on \(X\) (if \(|X|\) is even), and the existence of a non-crossing properly colored geometric spanning tree with maximum degree at most \(3\) on \(X\). Moreover, we show the existence of a non-crossing properly colored geometric perfect matching in the plane lattice. In order to prove these our results, we propose an useful lemma that gives a good partition of a sequence of multicolored points.
For the entire collection see [Zbl 1318.68008].

MSC:

05C15 Coloring of graphs and hypergraphs
05C62 Graph representations (geometric and intersection representations, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hoffmann, M.; Tóth, CD, Vertex-colored encompassing graphs, Graphs and Combinatorics, 30, 933-947 (2014) · Zbl 1298.05120 · doi:10.1007/s00373-013-1320-1
[2] Kaneko, A.; Akiyama, J.; Kano, M.; Urabe, M., On the maximum degree of bipartite embeddings of trees in the plane, Discrete and Computational Geometry, 166-171 (2000), Heidelberg: Springer, Heidelberg · Zbl 0959.05033 · doi:10.1007/978-3-540-46515-7_13
[3] Kaneko, A.; Kano, M.; Aronov, B.; Basu, S.; Pach, J.; Sharir, M., Discrete geometry on red and blue points in the plane — a survey —, Discrete and Computational Geometry, 551-570 (2003), Heidelberg: Springer, Heidelberg · Zbl 1079.52505 · doi:10.1007/978-3-642-55566-4_25
[4] Kano, M.; Suzuki, K.; Pach, J., Discrete geometry on red and blue points in the plane lattice, Thirty Essays on Geometric Graph Theory, 355-369 (2013), New York: Springer, New York · Zbl 1276.52014 · doi:10.1007/978-1-4614-0110-0_18
[5] Larson, LC, Problem-Solving Through Problems (1983), New York: Springer, New York · Zbl 0524.00004 · doi:10.1007/978-1-4612-5498-0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.