Vertex coloring complete multipartite graphs from random lists of size 2 |
| |
Authors: | Carl Johan Casselgren |
| |
Institution: | aDepartment of Mathematics, Umeå University, SE-901 87 Umeå, Sweden |
| |
Abstract: | Let Ks×m be the complete multipartite graph with s parts and m vertices in each part. Assign to each vertex v of Ks×m a list L(v) of colors, by choosing each list uniformly at random from all 2-subsets of a color set C of size σ(m). In this paper we determine, for all fixed s and growing m, the asymptotic probability of the existence of a proper coloring φ, such that φ(v)∈L(v) for all v∈V(Ks×m). We show that this property exhibits a sharp threshold at σ(m)=2(s−1)m. |
| |
Keywords: | List coloring Complete multipartite graph Random list |
本文献已被 ScienceDirect 等数据库收录! |
|