##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 785.05067

**Autor: ** Erdös, Paul; Chen, Guantao; Rousseau, C.C.; Schelp, R.H.

**Title: ** Ramsey problems involving degrees in edge-colored complete graphs of vertices belonging to monochromatic subgraphs. (In English)

**Source: ** Eur. J. Comb. 14, No.3, 183-189 (1993).

**Review: ** This note concerns the degrees of vertices in the monochromatic subgraphs guaranteed by Ramseyian theorems. There are two theorems, using colorings g of edges into colors red and blue. Given a graph G, let R be the graph of red edges and B the graph of blue edges. Let \deg_{G}(x) be the degree of the vertex x in G. Given a regular graph G on vertices x in X, let \Delta_{G} = **max**_{x in X} \deg_{G}(x)- **max**_{x in X} \deg_{G}(x). If we color the edges of G red and blue, then \Delta_{B} = \Delta_{R}, and we denote this common ``degree spread'' \Delta_{\gamma}, where \gamma is the coloring. The first theorem is a formula for the minimal degree spread of vertices in the monochromatic subgraphs guaranteed by Ramsey's theorem. Given a graph G and a 2-coloring \gamma of its vertices, let \deg_{R}(x) be the degree of x in R. The second theorem states that for any m, if n = n(m) is sufficiently large, then any 2-coloring of the clique K_{n} admits a monochromatic bipartite K_{n,m} with two vertices x and y such that \deg_{R}(x) = \deg_{R}(y). This is also true of cycles C_{m}.

**Reviewer: ** G.L.McColm (Tampa)

**Classif.: ** * 05C55 Generalized Ramsey theory

05C15 Chromatic theory of graphs and maps

**Keywords: ** monochromatic subgraphs; coloring; Ramsey's theorem

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag