Asymptotic game chromatic number conjecture for random graphs

Let Gn,pG_{n,p} be the random graph on nn vertices in which each edge is present independently with probability pp, and let χg(Gn,p)\chi_g(G_{n,p}) denote its game chromatic number. For a constant η>0\eta>0, assume that p1ηp\leq 1-\eta and npnp\to\infty, and write b=1/(1p)b=1/(1-p). Asymptotic game chromatic number conjecture. With high probability,

χg(Gn,p)=(1+o(1))nlogbnp.\chi_g(G_{n,p})=(1+o(1))\frac{n}{\log_b np}.

The conjecture proposes the asymptotically sharp value of the game chromatic number in the stated range of pp, improving the paper's upper and lower bounds, which differ only by a multiplicative constant. Its status is not resolved in the supplied source.

Sources & referencesView supporting material

Primary source

Tom Bohman, Alan Frieze and Benny Sudakov, “The game chromatic number of random graphs”, arXiv:0707.0465 (2007).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.