Asymmetric Coloring Games on Incomparability Graphs

详细信息    查看全文

• 作者：Tomasz Krawczyk¹ ; ^{krawczyk@tcs.uj.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Bartosz Walczak¹ ; ^{walczak@tcs.uj.edu.pl" class="auth_mail" title="E-mail the corresponding author}
• 关键词：game chromatic number ; Grundy number ; incomparability graphs
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2015
• 出版时间：November 2015
• 年：2015
• 卷：49
• 期：Complete
• 页码：803-811
• 全文大小：230 K

文摘

Consider the following game on a graph G: Alice and Bob take turns coloring the vertices of G properly from a fixed set of colors; Alice wins when the entire graph has been colored, while Bob wins when some uncolored vertices have been left. The game chromatic number of G is the minimum number of colors that allows Alice to win the game. The game Grundy number of G   is defined similarly except that the players color the vertices according to the first-fit rule and they only decide on the order in which it is applied. The $(a,b)\text{-}\mathit{g}\mathit{a}\mathit{m}\mathit{e}\mathit{c}\mathit{h}\mathit{r}\mathit{o}\mathit{m}\mathit{a}\mathit{t}\mathit{i}\mathit{c}$ and Grundy numbers are defined likewise except that Alice colors a vertices and Bob colors b   vertices in each round. We study the behavior of these parameters for incomparability graphs of posets with bounded width. We conjecture a complete characterization of the pairs (a,b)$(a,b)$ for which the (a,b)-game$(a,b)\text{-}\mathrm{game}$ chromatic and Grundy numbers are bounded in terms of the width of the poset; we prove that it gives a necessary condition and provide some evidence for its sufficiency. We also show that the game chromatic number is not bounded in terms of the Grundy number, which answers a question of Havet and Zhu.