Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Identifiers
URN: urn:nbn:se:liu:diva-107123DOI: 10.1002/rsa.20469ISI: 000333236500003OAI: oai:DiVA.org:liu-107123DiVA: diva2:722014
Available from: 2014-06-05 Created: 2014-06-05 Last updated: 2017-12-05

Open Access in DiVA

fulltext(215 kB)97 downloads
File information
File name FULLTEXT01.pdfFile size 215 kBChecksum SHA-512
b055966e0882af48b1dd42636048af0f0d74d4370496f66f6f072f8c30a9e8b56c29be2ce1d7f8023e4b2dbd31331b9a40dfa0cfea9593e9b55fee01d92b58ba
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: 97 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 118 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf