Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903065 | Discrete Mathematics | 2018 | 7 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
MaÅgorzata Bednarska-BzdÄga, Michael Krivelevich, Viola Mészáros, Clément Requilé,