Consider a game played on the edge set of the infinite clique by two players, Builder and Painter. In each round, Builder chooses an edge and Painter colours it red or blue. Builder wins by creating either a red copy of $G$ or a blue copy of $H$ for some fixed graphs $G$ and $H$. The minimum number of rounds within which Builder can win, assuming both players play perfectly, is the on-line Ramsey number $\tilde{r}(G,H)$. In this paper, we consider the case where $G$ is a path $P_k$. We prove that $\tilde{r}(P_3,P_{\ell+1}) = \lceil 5\ell/4\rceil = \tilde{r}(P_3,C_{\ell})$ for all $\ell \ge 5$, and determine $\tilde{r}(P_4,P_{\ell+1})$ up to an additive constant for all $\ell \ge 3$. We also prove some general lower bounds for on-line Ramsey numbers of the form $\tilde{r}(P_{k+1},H)$.
@article{10_37236_4097,
author = {Joanna Cyman and Tomasz Dzido and John Lapinskas and Allan Lo},
title = {On-line {Ramsey} numbers of paths and cycles},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {1},
doi = {10.37236/4097},
zbl = {1305.05138},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4097/}
}
TY - JOUR
AU - Joanna Cyman
AU - Tomasz Dzido
AU - John Lapinskas
AU - Allan Lo
TI - On-line Ramsey numbers of paths and cycles
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/4097/
DO - 10.37236/4097
ID - 10_37236_4097
ER -
%0 Journal Article
%A Joanna Cyman
%A Tomasz Dzido
%A John Lapinskas
%A Allan Lo
%T On-line Ramsey numbers of paths and cycles
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/4097/
%R 10.37236/4097
%F 10_37236_4097
Joanna Cyman; Tomasz Dzido; John Lapinskas; Allan Lo. On-line Ramsey numbers of paths and cycles. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/4097
