Coloring graphs from random lists of size 2

详细信息    查看全文

• 作者：Carl Johan Casselgren ^{carl-johan.casselgren@math.umu.se}
• 刊名：European Journal of Combinatorics
• 出版年：2012
• 出版时间：February, 2012
• 年：2012
• 卷：33
• 期：2
• 页码：168-181
• 全文大小：270 K

文摘

Let be a graph on vertices with girth at least and maximum degree bounded by some absolute constant . Assign to each vertex of a list of colors by choosing each list independently and uniformly at random from all 2-subsets of a color set of size . In this paper we determine, for each fixed and growing , the asymptotic probability of the existence of a proper coloring such that for all . In particular, we show that if is odd and , then the probability that has a proper coloring from such a random list assignment tends to 1 as . Furthermore, we show that this is best possible in the sense that for each fixed odd and each , there is a graph with bounded maximum degree and girth , such that if , then the probability that has a proper coloring from such a random list assignment tends to 0 as . 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 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 , exhibits a sharp threshold at .