Wyszukiwarka
Abstrakt
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)$.
Autorzy (4)
-
Tomasz Dzido
- Wydział Matematyki, Fizyki i Informatyki UG Instytut Informatyki
-
John Lapinskas
-
Allan Lo
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
ELECTRONIC JOURNAL OF COMBINATORICS
nr 22,
wydanie 1,
strony 1 - 32,
ISSN: 1077-8926 - Język:
- angielski
- Rok wydania:
- 2015
- Opis bibliograficzny:
- 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
- Źródła finansowania:
-
- COST_FREE
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 67 razy
Publikacje, które mogą cię zainteresować
Equitable coloring of corona products of graphs
- H. Furmańczyk,
- K. Kaliraj,
- M. Kubale
- + 1 autorów
On some Zarankiewicz numbers and bipartite Ramsey Numbers for Quadrilateral
- J. Dybizbański,
- T. Dzido,
- S. Radziszowski