Premium
Asymptotic bounds for irredundant and mixed Ramsey numbers
Author(s) -
Chen Guantao,
Hattingh Johannes H.,
Rousseau Cecil C.
Publication year - 1993
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190170208
Subject(s) - combinatorics , ramsey's theorem , mathematics , graph , element (criminal law) , upper and lower bounds , discrete mathematics , set (abstract data type) , computer science , political science , law , mathematical analysis , programming language
The irredundant Ramsey number s(m, n) is the smallest N such that in every red‐blue coloring of the edges of K N , either the blue graph contains an m ‐element irredundant set or the red graph contains an n ‐element irredundant set. The definition of the mixed Ramsey number t(m, n) differs from s(m, n) in that the n ‐element irredundant set is replaced by an n ‐element independent set. We prove asymptotic lower bounds for s(n, n) and t(m, n) (with m fixed and n large) and a general upper bound for t (3, n ). © 1993 John Wiley & Sons, Inc.