Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 794.05086
Autor: Erdös, Paul; Hattingh, Johannes H.
Title: Asymptotic bounds for irredundant Ramsey numbers. (In English)
Source: Quaest. Math. 16, No.3, 319-331 (1993).
Review: Let G(V,E) be a graph. A set of vertices X\subseteq V is said to be irredundant if each vertex x in X is either an isolated vertex in the subgraph induced by X or there is vertex y in V-X which is incident with x and no other vertex in X. The irredundant Ramsey number s(m,n) is the smallest positive integer s so that, in every red-blue coloring of the edges of the complete graph on s vertices, either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. The main result of this paper is
Theorem 1. For each m \geq 3 there is a positive constant Cm such that s(m,n) > Cm({n\over log n}){m2- m-1\over 2(m-1)}.
Reviewer: J.E.Graver (Syracuse)
Classif.: * 05C55 Generalized Ramsey theory
Keywords: bounds; irredundant Ramsey number
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag