ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2018-2019): c. 84%
Discussiones Mathematicae Graph Theory 25(1-2) (2005)
Andrzej Kurek and Andrzej Ruciński
Department of Discrete Mathematics
Adam Mickiewicz University
In the first part of this paper we show that when H is a complete graph Kk
on k vertices, then minf(H,r) = (R−1)/2, where R = R(k;r) is the classical
Ramsey number. As a corollary we derive a new proof of the result credited to
Chvatál that the size Ramsey number for Kk equals (R2).
We also study an on-line version of the size Ramsey number, related to the
following two-person game: Painter colors on-line the edges provided by Builder,
and Painter's goal is to avoid a monochromatic copy of Kk. The on-line
Ramsey number R(k;r) is the smallest number of moves (edges) in
which Builder can force Painter to lose if r colors are available. We show
that R(3;2) = 8
and R(k;2) ≤
leave unanswered the question if R(k;2) = o(R2(k;2)).
Keywords: size Ramsey number, graph density, online Ramsey games.
2000 Mathematics Subject Classification: 05C55, 05D10, 91A43.
Received 16 November 2003