liu.seSearch for publications in DiVA
Change search

Cite
Citation style
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• oxford
• 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 of various maximum degree from random lists
Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
2018 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 52, no 1, p. 54-73Article in journal (Refereed) Published
##### Abstract [en]

Let G=G(n) be a graph on n vertices with maximum degree = (n). Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all k-subsets of a color set C of size C sigma=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 ) of the existence of a proper coloring phi of G, such that phi(v)L(v) for every vertex v of G, a so-called L-coloring. We give various lower bounds on sigma, in terms of n, k, and , which ensures that with probability tending to 1 as n there is an L-coloring of G. In particular, we show, for all fixed k and growing n, that if sigma(n)=(n1/k21/k) and =O(n), then the probability that G has an L-coloring tends to 1 as n. If k2 and =(n1/2), then the same conclusion holds provided that sigma=(). We also give related results for other bounds on , when k is constant or a strictly increasing function of n.

##### Place, publisher, year, edition, pages
WILEY , 2018. Vol. 52, no 1, p. 54-73
##### Keywords [en]
coloring from random lists; list coloring; random list
##### National Category
Probability Theory and Statistics
##### Identifiers
ISI: 000415879600003OAI: oai:DiVA.org:liu-143607DiVA, id: diva2:1165638
##### Note

Funding Agencies|SVeFUM; Mittag-Leffler Institute

Available from: 2017-12-13 Created: 2017-12-13 Last updated: 2018-01-03

#### Open Access in DiVA

##### File information
File name FULLTEXT01.pdfFile size 294 kBChecksum SHA-512
Type fulltextMimetype application/pdf

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
Random structures & algorithms (Print)
##### On the subject
Probability Theory and Statistics

#### Search outside of DiVA

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: 91 hits

Cite
Citation style
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• oxford
• 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