Coloring arcs of convex sets

详细信息    查看全文

• 作者：Harborth ; Heiko ; Lefmann ; Hanno
• 关键词：Geometric graphs ; Ramsey numbers ; Paths and cycles
• 刊名：Discrete Mathematics
• 出版年：2000
• 出版时间：June 6, 2000
• 年：2000
• 卷：220
• 期：1-3
• 页码：107-117
• 全文大小：138 K

文摘

In this note we consider Ramsey-type problems on graphs whose vertices are represented by the vertices of a convex polygon in the Euclidean plane. The edges of the graph are represented by the segments between the points of the polygon. The edges are arbitrarily colored by a fixed number of colors and the problem is to decide whether there exist monochromatic subgraphs of certain types satisfying some geometric conditions. We will give lower and upper bounds for these geometric Ramsey numbers for certain paths and cycles and also some exact values. It turns out that the particular type of the embedding is crucial for the growth rate of the corresponding geometric Ramsey numbers. In particular, the Ramsey numbers for crossing 4-cycles and t colors grow quadratically in t, while for convex 4-cycles they grow at least exponentially.