On-line Ramsey numbers for paths and short cycles

Janusz Dybizbański , Tomasz Dzido , Renata Zakrzewska

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 colors it red or blue. Builder wins by creating either a red copy of or a blue copy of for some fixed graphs and . The minimum number of rounds within which Builder can win, assuming both players play perfectly, is the on-line Ramsey number r(G,H). In this paper, we prove some new general lower and upper bounds for on-line Ramsey numbers r(C3,Pk) and r(C4,Pk).
Publication typeIn press (online first, early view)
Author Janusz Dybizbański (FMPI/II)
Janusz Dybizbański,,
- Institute of Informatics
, Tomasz Dzido (FMPI/II)
Tomasz Dzido,,
- Institute of Informatics
, Renata Zakrzewska
Renata Zakrzewska,,
-
Journal seriesDiscrete Applied Mathematics, ISSN 0166-218X, e-ISSN 1872-6771, (N/A 70 pkt)
Issue year2020
Noonline first
Pages1-6
Publication size in sheets0.50
Keywords in Englishon-line Ramsey theory, combinatorial games, paths cycles
ASJC Classification2604 Applied Mathematics; 2607 Discrete Mathematics and Combinatorics
DOIDOI:10.1016/j.dam.2020.03.004
URL https://doi.org/10.1016/j.dam.2020.03.004
Languageen angielski
LicenseJournal (articles only); published final; Uznanie Autorstwa - Użycie Niekomercyjne - Bez utworów zależnych (CC-BY-NC-ND); with publication
Score (nominal)70
Score sourcejournalList
ScoreMinisterial score = 70.0, 13-03-2020, ArticleFromJournal
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.263; WoS Impact Factor: 2018 = 0.983 (2) - 2018=1.029 (5)
Citation count*
Cite
busy
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?