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 Complete and Complete Bipartite Graphs from Random Lists
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2016 (English)In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 32, no 2, 533-542 p.Article in journal (Refereed) Published
Resource type
Text
Abstract [en]

Assign to each vertex v of the complete graph on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set , where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as ) of the existence of a proper coloring of , such that for every vertex v of . We show that this property exhibits a sharp threshold at . Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph with parts of size m and n, respectively. We show that if , , and L is a random (f(n), [n])-list assignment for the line graph of , then with probability tending to 1, as , there is a proper coloring of the line graph of with colors from the lists.

Place, publisher, year, edition, pages
2016. Vol. 32, no 2, 533-542 p.
Keyword [en]
List coloring, Random list, Coloring from random lists, Complete graph, Complete bipartite graph
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-118388DOI: 10.1007/s00373-015-1587-5ISI: 000371081000007OAI: oai:DiVA.org:umu-118388DiVA: diva2:922402
Available from: 2016-04-22 Created: 2016-03-18 Last updated: 2016-04-22Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Häggkvist, Roland
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Graphs and Combinatorics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 46 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