Article ID Journal Published Year Pages File Type
4649659 Discrete Mathematics 2009 7 Pages PDF
Abstract

In a circular rr-colouring game on GG, Alice and Bob take turns colouring the vertices of GG with colours from the circle S(r)S(r) of perimeter rr. Colours assigned to adjacent vertices need to have distance at least 1 in S(r)S(r). Alice wins the game if all vertices are coloured, and Bob wins the game if some uncoloured vertices have no legal colour. The circular game chromatic number χcg(G)χcg(G) of GG is the infimum of those real numbers rr for which Alice has a winning strategy in the circular rr-colouring game on GG. This paper proves that for any graph GG, χcg(G)≤2colg(G)−2, where colg(G) is the game colouring number of GG. This upper bound is shown to be sharp for forests. It is also shown that for any graph GG, χcg(G)≤2χa(G)(χa(G)+1)χcg(G)≤2χa(G)(χa(G)+1), where χa(G)χa(G) is the acyclic chromatic number of GG. We also determine the exact value of the circular game chromatic number of some special graphs, including complete graphs, paths, and cycles.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,