Coloring graphs from random lists of size 2

Let G=G(n)G=G(n) be a graph on nn vertices with girth at least gg and maximum degree bounded by some absolute constant ΔΔ. Assign to each vertex vv of GG a list L(v)L(v) of colors by choosing each list independently and uniformly at random from all 2-subsets of a color set CC of size σ(n)σ(n). In this paper we determine, for each fixed gg and growing nn, the asymptotic probability of the existence of a proper coloring φφ such that φ(v)∈L(v)φ(v)∈L(v) for all v∈V(G)v∈V(G). In particular, we show that if gg is odd and σ(n)=ω(n1/(2g−2))σ(n)=ω(n1/(2g−2)), then the probability that GG has a proper coloring from such a random list assignment tends to 1 as n→∞n→∞. Furthermore, we show that this is best possible in the sense that for each fixed odd gg and each n≥gn≥g, there is a graph H=H(n,g)H=H(n,g) with bounded maximum degree and girth gg, such that if σ(n)=o(n1/(2g−2))σ(n)=o(n1/(2g−2)), then the probability that HH has a proper coloring from such a random list assignment tends to 0 as n→∞n→∞. A corresponding result for graphs with bounded maximum degree and even girth is also given. Finally, by contrast, we show that for a complete graph on nn vertices, the property of being colorable from random lists of size 2, where the lists are chosen uniformly at random from a color set of size σ(n)σ(n), exhibits a sharp threshold at σ(n)=2nσ(n)=2n.