Search: id:"swepub:oai:DiVA.org:umu-43323" >
Vertex coloring com...
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
Keyword
- List coloring; Complete multipartite graph; Random list
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database