2014/12/03 by Dan Hefetz, Michael Krivelevich, Hefetz, Dan +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1412.1346
openalex publication_date 2014/12/03 · arxiv created 2015/10/14 · arxiv updated 2015/10/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a finite set X, a family of sets \mathcal 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, \mathcal 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 to go back to 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 ∈ \mathcal 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 ∈ \mathcal 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.