کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903065 1632401 2018 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Proper colouring Painter-Builder game
ترجمه فارسی عنوان
مناسب رنگ آمیزی نقاشی ساز بازی
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We consider the following two-player game, parametrised by positive integers n and k. The game is played between Painter and Builder, alternately taking turns, with Painter moving first. The game starts with the empty graph on n vertices. In each round Painter colours a vertex of her choice by one of the k colours and Builder adds an edge between two previously unconnected vertices. Both players must adhere to the restriction that the game graph is properly k-coloured. The game ends if either all n vertices have been coloured, or Painter has no legal move. In the former case, Painter wins the game; in the latter one, Builder is the winner. We prove that the minimal number of colours k=k(n) allowing Painter's win is of logarithmic order in the number of vertices n. Biased versions of the game are also considered.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 3, March 2018, Pages 658-664
نویسندگان
, , , ,