Coloring Complete and Complete Bipartite Graphs from Random Lists
2016 (English)In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 32, no 2, 533-542 p.Article in journal (Refereed) PublishedText
Assign to each vertex v of the complete graph on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set , where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as ) of the existence of a proper coloring of , such that for every vertex v of . We show that this property exhibits a sharp threshold at . Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph with parts of size m and n, respectively. We show that if , , and L is a random (f(n), [n])-list assignment for the line graph of , then with probability tending to 1, as , there is a proper coloring of the line graph of with colors from the lists.
Place, publisher, year, edition, pages
SPRINGER JAPAN KK , 2016. Vol. 32, no 2, 533-542 p.
List coloring; Random list; Coloring from random lists; Complete graph; Complete bipartite graph
IdentifiersURN: urn:nbn:se:liu:diva-126248DOI: 10.1007/s00373-015-1587-5ISI: 000371081000007OAI: oai:DiVA.org:liu-126248DiVA: diva2:913454