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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s1cjn" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />C</alternatives> of size <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s1cmr" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />σ(n)</alternatives>. Such a list assignment is called a random<alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s1cf0" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(k, C)</alternatives>‐list assignment. In this paper, we are interested in determining the asymptotic probability (as <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s1ch3" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n→∞</alternatives>) of the existence of a proper coloring ϕ of G, such that <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s1c87" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />φ(v)∈L(v)</alternatives> for every vertex v of G. We show, for all fixed k and growing n, that if <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s1ccw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />σ(n)=ω(n1/k2)</alternatives>, then the probability that G has such a proper coloring tends to 1 as <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s1d2f" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n→∞</alternatives>. A similar result for complete graphs is also obtained: if <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s1d30" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />σ(n)≥1.223n</alternatives> and L is a random <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s1cxq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(3, C)</alternatives>‐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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s1g1x" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n→∞</alternatives>.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 317‐327, 2014