Change search
ReferencesLink to record
Permanent link

Direct link
Coloring Complete and Complete Bipartite Graphs from Random Lists
Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
Umeå University, Sweden.
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
SPRINGER JAPAN KK , 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:liu:diva-126248DOI: 10.1007/s00373-015-1587-5ISI: 000371081000007OAI: diva2:913454
Available from: 2016-03-21 Created: 2016-03-21 Last updated: 2016-05-27

Open Access in DiVA

fulltext(171 kB)10 downloads
File information
File name FULLTEXT01.pdfFile size 171 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Casselgren, Carl Johan
By organisation
Mathematics and Applied MathematicsFaculty of Science & Engineering
In the same journal
Graphs and Combinatorics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 10 downloads
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: 138 hits
ReferencesLink to record
Permanent link

Direct link