Circular game chromatic number of graphs |
| |
Authors: | Wensong Lin Xuding Zhu |
| |
Institution: | a Department of Mathematics, Southeast University, Nanjing 210096, PR China b Department of Applied Mathematics, National Sun Yat-sen University, Taiwan c National Center for Theoretical Sciences, Taiwan |
| |
Abstract: | In a circular r-colouring game on G, Alice and Bob take turns colouring the vertices of G with colours from the circle S(r) of perimeter r. Colours assigned to adjacent vertices need to have distance at least 1 in 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) of G is the infimum of those real numbers r for which Alice has a winning strategy in the circular r-colouring game on G. This paper proves that for any graph G, , where is the game colouring number of G. This upper bound is shown to be sharp for forests. It is also shown that for any graph G, χcg(G)≤2χa(G)(χa(G)+1), where χa(G) is the acyclic chromatic number of G. We also determine the exact value of the circular game chromatic number of some special graphs, including complete graphs, paths, and cycles. |
| |
Keywords: | Circular game chromatic number Game colouring number Acyclic chromatic number Graphs Forests Planar graphs |
本文献已被 ScienceDirect 等数据库收录! |
|