2017/01/03 by Casselgren, Carl Johan
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1701.00614
Let G=G(n) be a graph on n vertices with maximum degree Δ=Δ(n). Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all k-subsets of a color set C of size σ= σ(n). Such a list assignment is called a \emphrandom (k,C)-list assignment. In this paper, we are interested in determining the asymptotic probability (as n → ∞) of the existence of a proper coloring φ of G, such that φ(v) ∈ L(v) for every vertex v of G, a so-called L-coloring. We give various lower bounds on σ, in terms of n, k and Δ, which ensures that with probability tending to 1 as n → ∞ there is an L-coloring of G. In particular, we show, for all fixed k and growing n, that if σ(n) = ω(n1/k2 Δ1/k) and Δ=O(n(k-1)/(k(k3+ 2k2 - k +1))), then the probability that G has an L-coloring tends to 1 as n → ∞. If k≥ 2 and Δ= Ω(n1/2), then the same conclusion holds provided that σ=ω(Δ). We also give related results for other bounds on Δ, when k is constant or a strictly increasing function of n.