Abstract | ||
---|---|---|
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 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 ′ n . |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.disc.2007.08.013 | Discrete Mathematics |
Keywords | Field | DocType |
noncrossing alternating path,bicolored point set | Discrete mathematics,Combinatorics,Existential quantification,Convex position,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
308 | 19 | Discrete Mathematics |
ISBN | Citations | PageRank |
3-540-24528-6 | 10 | 0.93 |
References | Authors | |
12 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
jan kyncl | 1 | 97 | 18.56 |
János Pach | 2 | 2366 | 292.28 |
Géza Tóth | 3 | 581 | 55.60 |
J Kyncl | 4 | 12 | 1.31 |