For any two-colouring of the segments determined by 3n-3 points in general position in the plane, either the first colour class contains a triangle, or there is a noncrossing cycle of length n in the secondcolour class, and this result is tight. We also give a series of more general estimates on off-diagonal geometric graph Ramsey numbers in the same spirit. Finally we investigate the existence of large noncrossing monochromatic matchings in multicoloured geometric graphs.
Additional Metadata
Keywords Ramsey theory, geometric graphs, noncrossing matchings
MSC Generalized Ramsey theory (msc 05C55), Paths and cycles (msc 05C38)
THEME Logistics (theme 3)
Publisher Springer
Journal Graphs and Combinatorics
Project Spinoza prijs Lex Schrijver
Citation
Karolyi, G, & Rosta, V. (2007). On geometric graph Ramsey numbers. Graphs and Combinatorics , 25(3), 351–363.