The game chromatic number of a random hypergraph
classification
🧮 math.CO
keywords
gamehypergraphnumberchromaticcolorcolorsconsiderplayer
read the original abstract
We consider the following game, played on a $k$-uniform hypergraph $H$. There are $q$ colors available and two players take it in turns to color vertices. A partial coloring is proper if no edge is mono-chromatic. One player, A, wishes to color all the vertices and the other player, B, wishes to prevent this. The {\em game chromatic number} $\chi_g(H)$ is the minimum number of colors for which A has a winning strategy. We consider this in the context of a random $k$-uniform hypergraph and prove upper and lower bounds that hold w.h.p.
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.