Distance Graph Ramsey Sets

摘要

The distance graph D_(n,d) has the vertex set {1,2,... ,n} and two vertices are adjacent if their difference is at most d. For given graphs G and H the distance graph D_(n,d) has the arrow property D_(n,d) → (G, H) if in every two-coloring of the edges of D_(n,d) there is a subgraph G of the first color or a subgraph H of the second color. The Ramsey set r_D(G,H) contains the smallest pairs (n,d) for which D_(n,d) → (G,H). Distance graph Ramsey sets for P_3 versus P_t, K_s versus K_t, and K_(1,s) versus K_(1,t) are presented.