Combinatorics, Probability and Computing

Table of Contents - 1993 - Volume 2, Issue 03  

Research Article

Ramsey Problems with Bounded Degree Spread

G. Chena1 and R. H. Schelpa2

a1 North Dakota State University, Fargo, ND 58105

a2 Memphis State University, Memphis, TN 38152

Abstract

Let k be a positive integer, k ≥ 2. In this paper we study bipartite graphs G such that, for n sufficiently large, each two-coloring of the edges of the complete graph Kn gives a monochromatic copy of G, with some k of its vertices having the maximum degree of these k vertices minus the minimum degree of these k vertices (in the colored Kn) at most k − 2.

(Received March 11 1993)

(Revised July 23 1993)