Change search
ReferencesLink to record
Permanent link

Direct link
Coloring Complete and Complete Bipartite Graphs from Random Lists
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2016 (English)In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 32, no 2, 533-542 p.Article in journal (Refereed) PublishedText
Abstract [en]

Assign to each vertex v of the complete graph on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set , where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as ) of the existence of a proper coloring of , such that for every vertex v of . We show that this property exhibits a sharp threshold at . Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph with parts of size m and n, respectively. We show that if , , and L is a random (f(n), [n])-list assignment for the line graph of , then with probability tending to 1, as , there is a proper coloring of the line graph of with colors from the lists.

Place, publisher, year, edition, pages
2016. Vol. 32, no 2, 533-542 p.
Keyword [en]
List coloring, Random list, Coloring from random lists, Complete graph, Complete bipartite graph
National Category
Discrete Mathematics
URN: urn:nbn:se:umu:diva-118388DOI: 10.1007/s00373-015-1587-5ISI: 000371081000007OAI: diva2:922402
Available from: 2016-04-22 Created: 2016-03-18 Last updated: 2016-04-22Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Häggkvist, Roland
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Graphs and Combinatorics
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: 12 hits
ReferencesLink to record
Permanent link

Direct link