The fractional chromatic number of random graphs

For a simple graph G , let χ^⁎(G) be the fractional chromatic number of G . Graph coloring has a long history in the study of random graph theory and numerous bounds on the chromatic number have been reported for classical random graph models including binomial random graphs and random regular graphs. However, little is known when it comes to the fractional chromatic number except for the trivial bounds that are directly inherited from deterministic graph theory. Let r be a constant in this paper. For the random regular graph model G_n,r, we show that χ^⁎(G_n,r)≥k for a given rational number k with high probability if the degree r is no less than some integer r_k, which is the solution of a minimization problem over the unit interval. For the binomial random graph model G_n,r/n, we find that χ^⁎(G_n,r/n)≥k for a given rational number k with high probability if r is greater than a number rˆ_k, which is determined by an optimization problem over a probability measure on the unit interval.