umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Coloring Complete and Complete Bipartite Graphs from Random Lists
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
2016 (Engelska)Ingår i: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 32, nr 2, s. 533-542Artikel i tidskrift (Refereegranskat) Published
Resurstyp
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.

Ort, förlag, år, upplaga, sidor
2016. Vol. 32, nr 2, s. 533-542
Nyckelord [en]
List coloring, Random list, Coloring from random lists, Complete graph, Complete bipartite graph
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-118388DOI: 10.1007/s00373-015-1587-5ISI: 000371081000007OAI: oai:DiVA.org:umu-118388DiVA, id: diva2:922402
Tillgänglig från: 2016-04-22 Skapad: 2016-03-18 Senast uppdaterad: 2018-06-07Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Häggkvist, Roland

Sök vidare i DiVA

Av författaren/redaktören
Häggkvist, Roland
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
Graphs and Combinatorics
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 164 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf