zbMATH — the first resource for mathematics

Long alternating paths in bicolored point sets. (English) Zbl 1168.05320
Summary: Given \(n\) red and \(n\) blue points in convex position in the plane, we show that there exists a noncrossing alternating path of length \(n+c\sqrt{n/\log n}\). We disprove a conjecture of Erdős by constructing an example without any such path of length greater than \(4/3 n + c'\sqrt n\).

05C38 Paths and cycles
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Abellanas, M.; Garcia, J.; Hernández, G.; Noy, M.; Ramos, P., Bipartite embeddings of trees in the plane, (), 1-10, Also in: Discrete Appl. Math. 93 (1999) 141-148 · Zbl 0929.05021
[2] M. Abellanas, A. Garcia, F. Hurtado, J. Tejel, Caminos alternantes, in: X Encuentros de Geometría Computacional (in Spanish), Sevilla, 2003, pp. 7-12.
[3] Bárány, I.; Matoušek, J., Simultaneous partitions of measures by \(k\)-fans, Discrete comput. geom., 25, 317-334, (2001) · Zbl 0989.52009
[4] Bespamyatnikh, S.; Kirkpatrick, D.; Snoeyink, J., Generalizing ham sandwich cuts to equitable subdivisions, Discrete comput. geom., 24, 605-622, (2000) · Zbl 0966.68156
[5] Brass, P.; Moser, W.; Pach, J., Research problems in discrete geometry, (2005), Springer New York · Zbl 1086.52001
[6] Chrobak, M.; Karloff, H., A lower bound on the size of universal sets for planar graphs, SIGACT news, 20/4, 63-86, (1989)
[7] de Fraysseix, H.; Pach, J.; Pollack, R., How to draw a planar graph on a grid, Combinatorica, 10, 41-51, (1990) · Zbl 0728.05016
[8] Gritzmann, P.; Mohar, B.; Pach, J.; Pollack, R., Embedding a planar triangulation with vertices at specified points (solution to problem E3341), Amer. math. monthly, 98, 165-166, (1991)
[9] Ikeba, Y.; Perles, M.; Tamura, A.; Tokunaga, S., The rooted tree embedding problem into points on the plane, Discrete comput. geom., 11, 51-63, (1994) · Zbl 0791.05027
[10] Kaneko, A.; Kano, M., Discrete geometry on red and blue points in the plane—a survey, (), 551-570 · Zbl 1079.52505
[11] A. Kaneko, M. Kano, K. Suzuki, Path coverings of two sets of points in the plane, in: J. Pach (Ed.), Towards a Theory of Geometric Graphs, Contemp. Math. 342 (2004) 99-111. · Zbl 1064.52013
[12] Kaneko, A.; Kano, M.; Yoshimoto, K., Alternating Hamiltonian cycles with minimum number of crossings in the plane, Internat. J. comput. geom. appl., 10, 73-78, (2000) · Zbl 1074.68640
[13] Károlyi, Gy.; Pach, J.; Tóth, G.; Valtr, P., Ramsey-type results for geometric graphs II, Discrete comput. geom., 20, 375-388, (1998) · Zbl 0912.05046
[14] Merino, C.; Salazar, G.; Urrutia, J., On the length of longest alternating paths for multicolored point sets in convex position, Discrete math., 306, 15, 1791-1797, (2006) · Zbl 1101.05033
[15] Sakai, T., Balanced convex partitions of measures in \(R^2\), Graphs combin., 18, 169-192, (2002) · Zbl 1002.52002
[16] Tokunaga, S., On a straight-line embedding problem of graphs, Discrete math., 150, 371-378, (1996) · Zbl 0911.05030
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.