pith. sign in

arxiv: 1902.03130 · v1 · pith:IBRRE7ETnew · submitted 2019-02-06 · 🧮 math.CO

The game chromatic number of a random hypergraph

classification 🧮 math.CO
keywords gamehypergraphnumberchromaticcolorcolorsconsiderplayer
0
0 comments X
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.