Online and Connected Online Ramsey Numbers of a Matching versus a Path

Abstract

The (G1,G2)-online Ramsey game is a two-player turn-based game between a builder and a painter. Starting from an empty graph with infinite vertices, the builder adds a new edge in each round, and the painter colors it red or blue. The builder aims to force either a red copy of G1 or a blue copy of G2 in as few rounds as possible, while the painter’s aim is the opposite. The online Ramsey number r˜(G1,G2) is the minimum number of edges that the builder needs to win the (G1,G2)-online Ramsey game, regardless of the painter’s strategy. Furthermore, we initiate the study of connected online Ramsey game, which is identical to the usual one, except that at any time the graph induced by all edges should be connected. In this paper, we show a general bound of the online Ramsey number of a matching versus a path and determine its exact value when the path has an order of three or four. For the connected version, we obtain all connected online Ramsey numbers of a matching versus a path.

Keywords

• Ramsey number
• online Ramsey number
• connected online Ramsey number
• paths
• stars