Portal de Periódicos da CAPES

Waiter–Client and Client–Waiter planarity, colorability and minor games

2016; Elsevier BV; Volume: 339; Issue: 5 Linguagem: Inglês

10.1016/j.disc.2015.12.020

1872-681X

Dan Hefetz, Michael Krivelevich, Wei En Tan,

Advanced Topology and Set Theory

For a finite set X, a family of sets F⊆2X and a positive integer q, we consider two types of two player, perfect information games with no chance moves. In each round of the (1:q) Waiter–Client game (X,F), the first player, called Waiter, offers the second player, called Client, q+1 elements of the board X which have not been offered previously. Client then chooses one of these elements which he claims and the remaining q elements are claimed by Waiter. Waiter wins this game if by the time every element of X has been claimed by some player, Client has claimed all elements of some A∈F; otherwise Client is the winner. Client–Waiter games are defined analogously, the main difference being that Client wins the game if he manages to claim all elements of some A∈F and Waiter wins otherwise. In this paper we study the Waiter–Client and Client–Waiter versions of the non-planarity, Kt-minor and non-k-colorability games. For each such game, we give a fairly precise estimate of the unique integer q at which the outcome of the game changes from Client’s win to Waiter’s win. We also discuss the relation between our results, random graphs, and the corresponding Maker–Breaker and Avoider–Enforcer games.