Search
Abstract
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 \emph{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)$.
Authors (4)
-
Tomasz Dzido
- Wydział Matematyki, Fizyki i Informatyki UG Instytut Informatyki
-
John Lapinskas
-
Allan Lo
Cite as
Full text
- Publication version
- Accepted or Published Version
- License
-
open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
ELECTRONIC JOURNAL OF COMBINATORICS
no. 22,
edition 1,
pages 1 - 32,
ISSN: 1077-8926 - Language:
- English
- Publication year:
- 2015
- Bibliographic description:
- Cyman J., Dzido T., Lapinskas J., Lo A.: On-line Ramsey Numbers of Paths and Cycles// ELECTRONIC JOURNAL OF COMBINATORICS. -Vol. 22, iss. 1 (2015), s.1-32
- Sources of funding:
-
- Free publication
- Verified by:
- Gdańsk University of Technology
seen 114 times
Recommended for you
Equitable coloring of corona products of graphs
- H. Furmańczyk,
- K. Kaliraj,
- M. Kubale
- + 1 authors
On some Zarankiewicz numbers and bipartite Ramsey Numbers for Quadrilateral
- J. Dybizbański,
- T. Dzido,
- S. Radziszowski