کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648057 | 1342391 | 2011 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Vertex coloring complete multipartite graphs from random lists of size 2
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Vertex coloring complete multipartite graphs from random lists of size 2 Vertex coloring complete multipartite graphs from random lists of size 2](/preview/png/4648057.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issue 13, 6 July 2011, Pages 1150–1157
Journal: Discrete Mathematics - Volume 311, Issue 13, 6 July 2011, Pages 1150–1157
نویسندگان
Carl Johan Casselgren,