Name
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.disc.2017.11.008 | Discrete Mathematics |
Keywords | Field | DocType |
Combinatorial games,Graph colouring | Integer,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Painting,Null graph,Mathematics | Journal |
Volume | Issue | ISSN |
341 | 3 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Malgorzata Bednarska-Bzdega | 1 | 0 | 0.34 |
| michael krivelevich | 2 | 1688 | 179.90 |
| Viola Mészáros | 3 | 0 | 0.34 |
| Clément Requilé | 4 | 0 | 0.34 |