On-line Ramsey numbers for paths and short cycles. (English) Zbl 1441.05156
Summary: 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 colors 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 prove some new general lower and upper bounds for on-line Ramsey numbers \(\tilde{r} (C_3, P_k)\) and \(\tilde{r} (C_4, P_k)\).
In this paper, we prove some new general lower and upper bounds for on-line Ramsey numbers \(\tilde{r} (C_3, P_k)\) and \(\tilde{r} (C_4, P_k)\).
MSC:
| 05C57 | Games on graphs (graph-theoretic aspects) |
| 05C55 | Generalized Ramsey theory |
| 05D10 | Ramsey theory |
| 05C38 | Paths and cycles |
| 91A43 | Games involving graphs |
References:
| [1] | Beck, J., Achievement games and the probabilistic method, (Combinatorics, Paul Erdős is Eighty (1993), Bolyai Society of Mathematical Studies), 51-78 · Zbl 0806.90146 |
| [2] | Cyman, J.; Dzido, T., A note on on-line Ramsey numbers for quadrilaterals, Opuscula Math., 34, 463-468 (2014) · Zbl 1327.05226 |
| [3] | Cyman, J.; Dzido, T.; Lapinskas, J.; Lo, A., On-line Ramsey numbers for paths and cycles, Electron. J. Combin., 22 (2015), #P1.15 · Zbl 1305.05138 |
| [4] | T. Dzido, R. Zakrzewska, A note on on-line Ramsey numbers for some paths (submitted for publication). · Zbl 1131.05058 |
| [5] | Gordinowicz, P.; Prałat, P., Small on-line Ramsey numbers-a new approach, Contrib. Discrete Math., 13, 2, 101-111 (2018) · Zbl 1406.05108 |
| [6] | Grytczuk, J.; Kierstead, H.; Prałat, P., On-line Ramsey numbers for paths and stars, Discrete Math. Theor. Comput. Sci., 10, 3, 63-74 (2008) · Zbl 1196.05053 |
| [7] | Kurek, A.; Ruciński, A., Two variants of the size Ramsey number, Discuss. Math. Graph Theory, 25, 141-149 (2005) · Zbl 1074.05062 |
| [8] | Prałat, P., A note on small on-line Ramsey numbers for paths and their generalisations, Australas. J. Combin., 40, 27-36 (2008) · Zbl 1141.05061 |
| [9] | Prałat, P., \( \widetilde{r} ( K_3 , K_4 ) = 17\), Electron. J. Combin., 15 (2008), #R67, 13pp · Zbl 1159.05036 |
| [10] | Prałat, P., A note on off-diagonal small on-line Ramsey numbers for paths, Ars Combin., 107, 295-306 (2012) · Zbl 1289.05333 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
