کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649659 1342462 2009 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Circular game chromatic number of graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Circular game chromatic number of graphs
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 13, 6 July 2009, Pages 4495–4501
نویسندگان
, ,