Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648057 | Discrete Mathematics | 2011 | 8 Pages |
Abstract
Let Ks×mKs×m be the complete multipartite graph with ss parts and mm vertices in each part. Assign to each vertex vv of Ks×mKs×m a list L(v)L(v) of colors, by choosing each list uniformly at random from all 2-subsets of a color set CC of size σ(m)σ(m). In this paper we determine, for all fixed ss and growing mm, the asymptotic probability of the existence of a proper coloring φφ, such that φ(v)∈L(v)φ(v)∈L(v) for all v∈V(Ks×m)v∈V(Ks×m). We show that this property exhibits a sharp threshold at σ(m)=2(s−1)mσ(m)=2(s−1)m.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Carl Johan Casselgren,