
doi: 10.37236/1810
The Ramsey game we consider in this paper is played on an unbounded set of vertices by two players, called Builder and Painter. In one move Builder introduces a new edge and Painter paints it red or blue. The goal of Builder is to force Painter to create a monochromatic copy of a fixed target graph $H$, keeping the constructed graph in a prescribed class ${\cal G}$. The main problem is to recognize the winner for a given pair $H,{\cal G}$. In particular, we prove that Builder has a winning strategy for any $k$-colorable graph $H$ in the game played on $k$-colorable graphs. Another class of graphs with this strange self-unavoidability property is the class of forests. We show that the class of outerplanar graphs does not have this property. The question of whether planar graphs are self-unavoidable is left open. We also consider a multicolor version of Ramsey on-line game. To extend our main result for $3$-colorable graphs we introduce another Ramsey type game, which seems interesting in its own right.
Eigenvalues, singular values, and eigenvectors, Coloring of graphs and hypergraphs, \(k\)-colorable graph, Exact enumeration problems, generating functions, Ramsey theory, Generalized Ramsey theory, Ramsey game, Determinants, permanents, traces, other special matrix functions, Games involving graphs, Ramsey on-line game, Paths and cycles
Eigenvalues, singular values, and eigenvectors, Coloring of graphs and hypergraphs, \(k\)-colorable graph, Exact enumeration problems, generating functions, Ramsey theory, Generalized Ramsey theory, Ramsey game, Determinants, permanents, traces, other special matrix functions, Games involving graphs, Ramsey on-line game, Paths and cycles
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 19 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
