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 \degG(x) be the degree of the vertex x in G. Given a regular graph G on vertices x in X, let \DeltaG = maxx in X \degG(x)- maxx in X \degG(x). If we color the edges of G red and blue, then \DeltaB = \DeltaR, 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 \degR(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 Kn admits a monochromatic bipartite Kn,m with two vertices x and y such that \degR(x) = \degR(y). This is also true of cycles Cm.
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