Online Ramsey theory for planar graphs
The electronic journal of combinatorics, Tome 21 (2014) no. 1
An online Ramsey game $(G,\mathcal{H})$ is a game between Builder and Painter, alternating in turns. During each turn, Builder draws an edge, and Painter colors it blue or red. Builder's goal is to force Painter to create a monochromatic copy of $G$, while Painter's goal is to prevent this. The only limitation for Builder is that after each of his moves, the resulting graph has to belong to the class of graphs $\mathcal{H}$. It was conjectured by Grytczuk, Hałuszczak, and Kierstead (2004) that if $\mathcal{H}$ is the class of planar graphs, then Builder can force a monochromatic copy of a planar graph $G$ if and only if $G$ is outerplanar. Here we show that the "only if" part does not hold while the "if" part does.
DOI :
10.37236/2940
Classification :
05C55, 05C10, 05C57, 91A43
Mots-clés : Ramsey theory, online Ramsey games, planar graphs, outerplanar graphs, game theory, builder and painter
Mots-clés : Ramsey theory, online Ramsey games, planar graphs, outerplanar graphs, game theory, builder and painter
Affiliations des auteurs :
Šárka Petříčková 1
@article{10_37236_2940,
author = {\v{S}\'arka Pet\v{r}{\'\i}\v{c}kov\'a},
title = {Online {Ramsey} theory for planar graphs},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {1},
doi = {10.37236/2940},
zbl = {1300.05175},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2940/}
}
Šárka Petříčková. Online Ramsey theory for planar graphs. The electronic journal of combinatorics, Tome 21 (2014) no. 1. doi: 10.37236/2940
Cité par Sources :