liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
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
URN: urn:nbn:se:liu:diva-143607DOI: 10.1002/rsa.20725ISI: 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

The full text will be freely available from 2018-08-20 15:11
Available from 2018-08-20 15:11

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

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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

Direct link
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