首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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, View the MathML source, where View the MathML source 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号