DIKUL - logo
E-viri
  • Planarity, Colorability, an...
    Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš; Szabó, Tibor

    SIAM journal on discrete mathematics, 01/2008, Letnik: 22, Številka: 1
    Journal Article

    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 $b$ 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 $K_t$-minor game.