ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Mathematicae Graph Theory 19(1) (1999) 93-110DOI: 10.7151/dmgt.1088
Department of Mathematics, University of Victoria
P.O. Box 3045, Victoria, BC, CANADA V8W 3P4
Department of Mathematics, University of South Africa
P.O. Box 392, Pretoria, South Africa 0003
A set X of vertices of a graph G is said to be 1-dependent if the subgraph of G induced
by X has maximum degree one. The 1-dependent Ramsey number t1(l,m) is the
smallest integer n such that for any 2-edge colouring (R,B) of Kn, the spanning
subgraph B of Kn has a 1-dependent set of size l or the subgraph R has a
1-dependent set of size m. The 2-edge colouring (R,B) is a t1(l,m) Ramsey
colouring of Kn if B (R, respectively) does not contain a 1-dependent set of
size l (m, respectively); in this case R is also called a (l,m,n) Ramsey graph. We show
that t1(4,5) = 9, t1(4,6) = 11, t1(4,7) = 16 and t1(4,8)
= 17. We also determine all (4,4,5), (4,5,8), (4,6,10) and (4,7,15) Ramsey graphs.
Keywords: 1-dependence, irredundance, CO-irredundance, Ramsey numbers.
1991 Mathematics Subject Classification: 05C55, 05C70.
Received 14 July 1998
Revised 12 April 1999