Variations in Ramsey Theory

Book excerpt: The Ramsey number R(F,H) of two graphs F and H is the smallest positive integer n for which every red-blue coloring of the (edges of a) complete graph of order n results in a graph isomorphic to F all of whose edges are colored red (a red F) or a blue H. Beineke and Schwenk extended this concept to a bipartite version of Ramsey numbers, namely the bipartite Ramsey number BR(F,H) of two bipartite graphs F and H is the smallest positive integer r such that every red-blue coloring of the r-regular complete bipartite graph results in either a red F or a blue H. Chartrand extended this further to a multipartite version. Bialostocki and Voxman introduced the rainbow Ramsey number RR(G) of a graph G as the smallest positive integer n such that if every edge of the complete graph of order n is colored from any number of colors, then either a monochromatic G (all edges of G colored the same) or a rainbow G (no two edges of G colored the same) results. Eroh extended this concept from one graph to two graphs. These concepts are generalized even further in this work. We present results and open questions concerning several new variations of Ramsey numbers as well as their connections with some well-known concepts in chromatic graph theory.