On geometric graph Ramsey numbers
Graphs and Combinatorics , Volume 25 - Issue 3 p. 351- 363
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.
|Keywords||Ramsey theory, geometric graphs, noncrossing matchings|
|MSC||Generalized Ramsey theory (msc 05C55), Paths and cycles (msc 05C38)|
|THEME||Logistics (theme 3)|
|Journal||Graphs and Combinatorics|
|Project||Spinoza prijs Lex Schrijver|
Karolyi, G, & Rosta, V. (2007). On geometric graph Ramsey numbers. Graphs and Combinatorics , 25(3), 351–363.