Change search
ReferencesLink to record
Permanent link

Direct link
Coloring graphs from random lists of fixed size
Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, The Institute of Technology.
2014 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 44, no 3, 317-327 p.Article in journal (Refereed) Published
Abstract [en]

Let G = G(n) be a graph on n vertices with maximum degree bounded by some absolute constant Delta. Assign to each vertex v of G a list L(v) of colors by choosing each list uniformly at random from all k-subsets of a color set C of size sigma(n). Such a list assignment is called a random (k,C)-list assignment. In this paper, we are interested in determining the asymptotic probability (as n -greater thaninfinity) of the existence of a proper coloring phi of G, such that phi(v)is an element of L(v) for every vertex v of G. We show, for all fixed k and growing n, that if sigma(n)=omega(n1/k2), then the probability that G has such a proper coloring tends to 1 as n -greater thaninfinity. A similar result for complete graphs is also obtained: if sigma(n)greater than= 1. 223n and L is a random (3,C)-list assignment for the complete graph K-n on n vertices, then the probability that K-n has a proper coloring with colors from the random lists tends to 1 as n -greater than infinity

Place, publisher, year, edition, pages
Wiley , 2014. Vol. 44, no 3, 317-327 p.
Keyword [en]
random list; list coloring
National Category
Natural Sciences
URN: urn:nbn:se:liu:diva-107123DOI: 10.1002/rsa.20469ISI: 000333236500003OAI: diva2:722014
Available from: 2014-06-05 Created: 2014-06-05 Last updated: 2014-12-03

Open Access in DiVA

fulltext(215 kB)56 downloads
File information
File name FULLTEXT01.pdfFile size 215 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 MathematicsThe Institute of Technology
In the same journal
Random structures & algorithms (Print)
Natural Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 56 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: 89 hits
ReferencesLink to record
Permanent link

Direct link