Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647125 | Discrete Mathematics | 2016 | 12 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Dan Hefetz, Michael Krivelevich, Wei En Tan,