Small on-line Ramsey numbers---a new approach
In this note, we revisit the problem of calculating small on-line Ramsey numbers R(G,H). A new approach is proposed that reduces the running time of the algorithm determining that R(K_3,K_4)=17 by a factor of at least 2*10^6 comparing to the previously used approach. Using high performance computing networks, we determined that R(K_4,K_4) <= 26, R(K_3,K_5) < 25, and that R(K_3,K_3,K_3) <= 20 for a natural generalization to three colours. All graphs on 3 or 4 vertices are investigated as well, including non-symmetric cases.
2. D. Conlon, On-line Ramsey numbers, SIAM J. Discrete Math. 23 (2009), 1954-1963.
3. J. Cyman and T. Dzido, A note on on-line Ramsey numbers for quadrilaterals, Opuscula Mathematica 34 (2014), 463-468.
4. J. Cyman, T. Dzido, J. Lapinskas, and A. Lo, On-line Ramsey number of paths and cycles, Electronic Journal of Combinatorics 22 (2015), #P1.15.
5. E. Friedgut, Y. Kohayakawa, V. Rödl, A. Ruciński, and P. Tetali, Ramsey games against one-armed bandit, Combin. Probab. Comput. 12 (2003), 515-545.
6. P. Gordinowicz and P. Prałat, programs written in C/C++ can be downloaded from http://www.math.ryerson.ca/~pralat/ or http://im0.p.lodz.pl/~pgordin/.
7. J. Grytczuk, H. Kierstead, and P. Prałat, On-line Ramsey numbers for paths and stars, Discrete Mathematics and Theoretical Computer Science 10 (2008), 63-74.
8. A. Kurek and A. Ruciński, Two variants of the size Ramsey number, Discuss. Math. Graph Theory 25 (2005), no. 1-2, 141-149.
9. B. D. McKay, nauty Users Guide (Version 2.5), http://cs.anu.edu.au/~bdm/nauty/.
10. B. D. McKay, Practical graph isomorphism, Congressus Numerantium 30 (1981), 45-87.
11. B. D. McKay and A. Piperno, Practical graph isomorphism II, J. Symbolic Computation 60 (2013), 94-112.
12. P. Prałat, A note on small on-line Ramsey numbers for paths and their generalization, Australasian Journal of Combinatorics 40 (2008), 27-36.
13. P. Prałat, R(3; 4) = 17, Electronic Journal of Combinatorics 15 (2008), #R67, 13pp.
14. P. Prałat, A note on off-diagonal small on-line ramsey numbers for paths, Ars Combinatoria 107 (2012), 295-306.
15. S. Radziszowski, Small Ramsey numbers, Electron. J. Combin. Dynamic Survey DS1 (2014), 94, revision #14.
16. D. B. West, Introduction to graph theory, 2nd ed., Prentice Hall, 2001.