Distance ramsey numbers

Abstract

If the vertices of the complete graph are labeled by 1, 2, . . . , n then a distance coloring is a 2-coloring of the edges of K_n such that two edges have the same color if the absolute differences of their vertex labels are equal. There are more distance colorings than circulant colorings. For small graphs the values of the corresponding distance Ramsey numbers are determined by computer. These values improve the known lower bounds of the classical Ramsey numbers R(K₅, K₈) [2], R(K₄, K₁₁), and R(K_2,2,2) and give new bounds for some bipartite graphs, the cube graph, and the Petersen graph.