Coloring graphs from random lists of fixed size. Issue 3 (24th September 2012) - Casselgren, Carl Johan
Abstract Let G = G(n) be a graph on n vertices with maximum degree bounded by some absolute constant Δ. Assign to each vertex v of G a list L(v) of colors by choosing each list uniformly at random from all k‐subsets of a color set C of size σ(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. We show, for all fixed k and growing n, that if σ(n)=ω(n1/k2), then the probability that G has such a proper coloring tends to 1 as n→∞. A similar result for complete graphs is also obtained: if σ(n)≥1.223n and L is a random (3, C)‐list assignment for the complete graph Kn on n vertices, then the probability that Kn has a proper coloring with colors from the random lists tends to 1 as n→∞.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 317‐327, 2014