pith. sign in

arxiv: 1503.04748 · v1 · pith:EY2OWGHHnew · submitted 2015-03-16 · 🧮 math.CO · cs.DM

Asymmetric coloring games on incomparability graphs

classification 🧮 math.CO cs.DM
keywords gamenumberverticesalicechromaticcolorsgrundybounded
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.