umu.sePublications
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 size 2
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2012 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 33, no 2, 168-181 p.Article in journal (Refereed) Published
Abstract [en]

Let G = G(n) be a graph on n vertices with girth at least g and 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 independently and uniformly at random from all 2-subsets of a color set e of size sigma (n). In this paper we determine, for each fixed g and growing n, the asymptotic probability of the existence of a proper coloring phi such that phi(v) is an element of L(v) for all v is an element of V(G). In particular, we show that if g is odd and sigma (n) = omega(n(1/(2g-2))), then the probability that G has a proper coloring from such a random list assignment tends to 1 as n --> infinity. Furthermore, we show that this is best possible in the sense that for each fixed odd g and each n >= g, there is a graph H = H(n, g) with bounded maximum degree and girth g, such that if sigma (n) = 0(n(1/(2g-2))), then the probability that H has a proper coloring from such a random list assignment tends to 0 as n --> infinity. A corresponding result for graphs with bounded maximum degree and even girth is also given. Finally, by contrast, we show that for a complete graph on n vertices, the property of being colorable from random lists of size 2, where the lists are chosen uniformly at random from a color set of size sigma (n), exhibits a sharp threshold at sigma (n) = 2n. (C) 2011 Elsevier Ltd. All rights reserved.

Place, publisher, year, edition, pages
London: Academic Press, 2012. Vol. 33, no 2, 168-181 p.
National Category
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-50912DOI: 10.1016/j.ejc.2011.09.040ISI: 000297890300005OAI: oai:DiVA.org:umu-50912DiVA: diva2:471492
Available from: 2012-01-02 Created: 2012-01-02 Last updated: 2017-12-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Casselgren, Carl Johan
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
European journal of combinatorics (Print)
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 37 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