Change search
ReferencesLink to record
Permanent link

Direct link
Vertex coloring complete multipartite graphs from random lists of size 2
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2011 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 311, no 13, 1150-1157 p.Article in journal (Refereed) Published
Abstract [en]

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 vV(Ks×m). We show that this property exhibits a sharp threshold at σ(m)=2(s−1)m.

Place, publisher, year, edition, pages
2011. Vol. 311, no 13, 1150-1157 p.
Keyword [en]
List coloring; Complete multipartite graph; Random list
National Category
URN: urn:nbn:se:umu:diva-43323DOI: 10.1016/j.disc.2010.07.013OAI: diva2:413020
Available from: 2011-04-27 Created: 2011-04-27 Last updated: 2011-09-28Bibliographically approved
In thesis
1. On some graph coloring problems
Open this publication in new window or tab >>On some graph coloring problems
2011 (English)Doctoral thesis, comprehensive summary (Other academic)
Place, publisher, year, edition, pages
Umeå: Umeå universitet, Institutionen för matematik och matematisk statistik, 2011. 22 p.
Doctoral thesis / Umeå University, Department of Mathematics, ISSN 1102-8300 ; 48
List coloring, interval edge coloring, coloring graphs from random lists, biregular graph, avoiding arrays, Latin square, scheduling
National Category
Discrete Mathematics
Research subject
urn:nbn:se:umu:diva-43389 (URN)978-91-7459-198-9 (ISBN)
Public defence
2011-05-20, MIT-huset, MA121, Umeå universitet, Umeå, 13:15
Available from: 2011-04-29 Created: 2011-04-28 Last updated: 2011-05-20Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Casselgren, Carl Johan
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 35 hits
ReferencesLink to record
Permanent link

Direct link