Daniel Johnston

Perhaps the best known concept in Extremal Graph Theory is the Ramseynumber. Ared-blue coloringof a graphGassigns every edge ofGthe color red orblue. For two graphs F and H, the Ramsey number R(F, H) of F and H is thesmallest positive integer n such that for every red-blue coloring of the completegraph K n of order n, there is either a subgraph F all of whose edges are colored red (are d F) or a subgraph H all of whose edges are colored blue (a blue H). In the case where F and H are bipartite (those having no cycles with an odd number ofvertices), the bipartite Ramsey number BR(F, H) was defined by Beineke andSchwenk in 1975 as the smallest positive integerrsuch that every red-blue coloringof ther-regular complete bipartite graph Kr, r results in a red For a blue H.

We look at an extension of this idea. For an integer k ≥ 2, a balanced complete k-partite graph of order n≥kis the completek-partite graph in whichevery partite set has eitherbn/kcordn/kevertices. For bipartite graphsFandHand an integerk with 2≤k≤R(F, H), the k-Ramsey number Rk(F, H) was defined by Chart r and and Zhang in 2013 as the smallest positive integernsuch that every red-blue coloring of a balanced completek-partite graph of order n produces either a red F or a blue H. This concept provides a new look at the well-known concept of Ramsey numbers and gives rise to some interesting questions.