کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647125 | 1342329 | 2016 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Waiter-Client and Client-Waiter planarity, colorability and minor games
ترجمه فارسی عنوان
عادت مشتری و مشتری و اظهارنظر، شایستگی، رنگ پذیری و بازی های جزئی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بازی های موقعیتی پلاناریته، رنگ آمیزی، افراد زیر سن قانونی،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 5, 6 May 2016, Pages 1525-1536
Journal: Discrete Mathematics - Volume 339, Issue 5, 6 May 2016, Pages 1525-1536
نویسندگان
Dan Hefetz, Michael Krivelevich, Wei En Tan,