Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/15849
Title: | Planarity, colorability, and minor games | Authors: | Hefetz D. Krivelevich M. Stojaković, Miloš Szabó T. |
Issue Date: | 1-Dec-2008 | Journal: | SIAM Journal on Discrete Mathematics | Abstract: | Let m and b be positive integers, and let F be a hypergraph. In an (m, b) Maker-Breaker game F two players, called Maker and Breaker, take turns selecting previously unclaimed vertices of F. Maker selects m vertices per move, and Breaker selects 6 vertices per move. The game ends when every vertex has been claimed by one of the players. Maker wins if he claims all of the vertices of some hyperedge of F; otherwise Breaker wins. An (m, b) Avoider-Enforcer game F is played in a similar way. The only difference is in the determination of the winner: Avoider loses if he claims all of the vertices of some hyperedge of F; otherwise Enforcer loses. In this paper we consider the Maker-Breaker and Avoider-Enforcer versions of the planarity game, the k-colorability game, and the Kt-minor game. © 2008 Society for Industrial and Applied Mathematics. | URI: | https://open.uns.ac.rs/handle/123456789/15849 | ISSN: | 08954801 | DOI: | 10.1137/060654414 |
Appears in Collections: | PMF Publikacije/Publications |
Show full item record
SCOPUSTM
Citations
28
checked on May 10, 2024
Page view(s)
16
Last Week
14
14
Last month
0
0
checked on May 3, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.