An online Ramsey game is a game between Builder and Painter, alternating in turns. In each round Builder draws an edge and Painter colors it either red or blue. Builder wins if after some round there is a monochromatic copy of the fixed graph H, otherwise Painter is the winner. In this thesis we investigate the computational complexity of the related decision problem and we show that it is PSPACE-complete. Moreover, we study a version of the game when Builder can draw only planar graphs and a generalization of the game for hypergraphs. We found a new class of graphs unavoidable on planar graphs. We provide a result showing that Builder wins the online Ramsey game on 3-uniform hyperforests when the goal graph H is 1-degenerate. 1
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:335236 |
| Date | January 2015 |
| Creators | Dvořák, Pavel |
| Contributors | Valla, Tomáš, Koucký, Michal |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/masterThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0023 seconds