Home > Search Results: keywords:"online Ramsey game complexity strategy"
Search:
 
Search Tips :: Simple Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 1 records found  Search took 0.01 seconds. 
Online Ramsey Theory
 Dvořák, Pavel ; Valla, Tomáš (advisor) ; Koucký, Michal (referee)
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
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English