Coloring graphs of various maximum degree from random lists. Issue 1 (20th August 2017) - Casselgren, Carl Johan
Abstract: 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 C σ = σ ( n ) . Such a list assignment is called a random ( 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 ) = ω ( n 1 / k 2 Δ 1 / k ) and Δ = O ( n k − 1 k ( k 3 + 2 k 2 − k + 1 ) ), then the probability that G has an L ‐coloring tends to 1 as n → ∞ . If k ≥ 2 and Δ = Ω ( n 1 / 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 .