Coloring graphs from random lists of fixed size
2014 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 44, no 3, 317-327 p.Article in journal (Refereed) Published
Let G = G(n) be a graph on n vertices with maximum degree bounded by some absolute constant Delta. 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 sigma(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 -greater thaninfinity) of the existence of a proper coloring phi of G, such that phi(v)is an element of L(v) for every vertex v of G. We show, for all fixed k and growing n, that if sigma(n)=omega(n1/k2), then the probability that G has such a proper coloring tends to 1 as n -greater thaninfinity. A similar result for complete graphs is also obtained: if sigma(n)greater than= 1. 223n and L is a random (3,C)-list assignment for the complete graph K-n on n vertices, then the probability that K-n has a proper coloring with colors from the random lists tends to 1 as n -greater than infinity
Place, publisher, year, edition, pages
Wiley , 2014. Vol. 44, no 3, 317-327 p.
random list; list coloring
IdentifiersURN: urn:nbn:se:liu:diva-107123DOI: 10.1002/rsa.20469ISI: 000333236500003OAI: oai:DiVA.org:liu-107123DiVA: diva2:722014