2015/03/16 by Tomasz Krawczyk, Krawczyk, Tomasz, Bartosz Walczak +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1503.04748
arxiv created 2015/03/16 · arxiv updated 2015/03/17
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)-game chromatic 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) for which the (a,b)-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.